Le problème Il n'y a pas de moyen facile d'obtenir une permutation avec une expression régulière. Permutation: obtenir un mot ("aabc") dans un autre ordre, sans changer le nombre ou le type de lettres.w=x1…xnw=x1…xnw=x_1…x_n Regex: expression régulière. Pour vérification: "Permutations d'expression...
Je pensais aux grammaires pour les langues sensibles à l'indentation et il semble que les grammaires CF feraient l'affaire si elles étaient combinées avec des paramètres. À titre d'exemple, considérons ce fragment pour la grammaire Python simplifiée au format de type ANTLR: // on top-level the...
Il existe de nombreuses langues populaires. Mais, les informaticiens nous disent que pour comprendre le comportement des programmes dans ces langues argumenter définitivement et sans ambiguïté sur le comportement du programme (par exemple prouver leur identité), nous devons les traduire dans un...
En faisant le travail actuel pour mon cours de langues formelles et d'automates, je suis resté coincé sur des exercices impliquant des langues unaires (j'espère que c'est le bon terme), c'est-à-dire des langues qui s'appuient sur une seule lettre. Je ne veux pas poser de questions sur les exercices...
Je recherche un algorithme efficace pour le problème suivant ou une preuve de dureté NP. Soit ΣΣ\Sigma un ensemble et A ⊆ P ( Σ )A⊆P(Σ)A\subseteq\mathcal{P}(\Sigma) un ensemble de sous-ensembles de ΣΣ\Sigma . Trouver une séquence w ∈ Σ ∗w∈Σ∗w\in \Sigma^* de moindre longueur telle que pour chaque L...
Je sais qu'il existe des langages non réguliers, de sorte que est régulier, mais tous les exemples que je peux trouver sont sensibles au contexte mais pas libres de contexte.L∗L∗L^* Au cas où il n'y en aurait pas comment le
J'étudie les langages formels et les systèmes de bases de production (systèmes de bases de règles) et je suis un peu confus quant à la raison pour laquelle ces deux mots "production" et "règle" signifient la même chose dans tant de contexte en informatique. En langue anglaise, ils ne semblent pas...
Il semble que les «expressions régulières de base» telles que définies par POSIX.1-2008 ne prennent pas en charge l'alternance a|b(bien que certaines implémentations grep reconnaissent la version échappée \|). Les langues régulières étant fermées par union par définition, cela signifie-t-il que...
LLL est une langue régulière sur l'alphabet . Le quotient gauche de concernant est le langage L w ∈ Σ ∗ w - 1 L : = { v ∣ w v ∈ L }Σ={a,b}Σ={a,b}\Sigma = \{a,b\}LLLw∈Σ∗w∈Σ∗w \in \Sigma^*w−1L:={v∣wv∈L}w−1L:={v∣wv∈L}w^{-1} L := \{v \mid wv \in L\} Comment puis-je prouver que est...
J'adorerais vraiment votre aide avec les éléments suivants: Pour tout fixe, je dois décider s'il y a fermeture sous les opérateurs suivants:L2L2L_2 Ar(L)={x∣∃y∈L2:xy∈L}Ar(L)={x∣∃y∈L2:xy∈L}A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\} Al(L)={x∣∃y∈L:xy∈L2}Al(L)={x∣∃y∈L:xy∈L2}A_l(L)=\{x \mid \exists...
Je suis tombé sur cette figure qui montre que les langages sans contexte et réguliers sont des sous-ensembles (appropriés) de problèmes efficaces (supposément ). Je comprends parfaitement que les problèmes efficaces sont un sous-ensemble de tous les problèmes décidables car nous pouvons les...
Existe-t-il des langages indécidables tels que leur union / intersection / langage concaténé est décidable? Quelle est l'interprétation physique d'un tel exemple car en général, les langages indécidables ne sont pas fermés sous ces opérations? Que dire de la fermeture de Kleene? En avons-nous aussi...
Je souhaite convertir une expression régulière entrée par l'utilisateur en NFA afin de pouvoir ensuite exécuter le NFA sur une chaîne à des fins de correspondance. Quelle est la machine minimale qui peut être utilisée pour analyser des expressions régulières? Je suppose que ce doit être un automate...
Je comprends que les grammaires sans contexte peuvent être utilisées pour représenter des langues sans contexte, ce qui peut avoir des ambiguïtés. Nous avons également des formes normales comme la forme normale de Chomsky et Greibach . Je ne pouvais pas comprendre le besoin de cela. Pourquoi...
Dites, L⊆{0}∗L⊆{0}∗L \subseteq \{0\}^* . Comment alors prouver que L∗L∗L^* est régulier? Si LLL est régulier, alors bien sûr L∗L∗L^* est également régulier. Si LLL est fini, alors il est régulier et encore L∗L∗L^* est régulier. J'ai également remarqué que, pour L={0p∣p is a prime}L={0p∣p is a...
Si est régulier, cela signifie-t-il que est régulier?A2A2A^2AAA Ma tentative de preuve: Oui, car la contradiction suppose que n'est pas régulier. Ensuite .AAAA2=A⋅AA2=A⋅AA^2 = A \cdot A Comme la concaténation de deux langues non régulières n'est pas régulière, ne peut pas être régulier. Cela...
Je me demande quelle est la complexité temporelle de la détermination du vide pour les DFA bidirectionnels? Autrement dit, des automates finis qui peuvent reculer sur leur bande d'entrée en lecture seule. Selon Wikipedia, ils sont équivalents aux DFA, bien que les DFA équivalents puissent être...
Je pensais que toutes les langues régulières pouvaient être exprimées avec des expressions régulières (si une langue est régulière, elle peut être exprimée avec regex), mais on m'a dit que vous avez besoin des trois opérations régulières (concaténation, union et étoile) pour cela tenir. Par...
Soit régulier, régulier, non régulier. Montrez que n'est pas régulier ou donnez un contre-exemple.L1L1L_1L1∩L2L1∩L2L_1 \cap L_2L2L2L_2L1∪L2L1∪L2L_1 \cup L_2 J'ai essayé ceci: Regardez . Celui-ci est régulier. Je peux construire un automate fini pour cela: est régulier, est régulier, donc supprimez...
Je veux prouver que le complément de { 0n1n∣ n ≥0 }{0n1n∣n≥0}\{0^n1^n \mid n \geq{} 0\} n'est pas régulier en utilisant des propriétés de fermeture. Je comprends que le lemme de pompage peut être utilisé pour prouver que { 0n1n∣ n ≥0 }{0n1n∣n≥0}\{0^n1^n \mid n \geq{} 0\}n'est pas une langue...