Questions sur les propriétés de la classe des langues régulières et des langues individuelles.
Il existe de nombreuses méthodes pour prouver qu'une langue n'est pas régulière , mais que dois-je faire pour prouver qu'une langue est régulière? Par exemple, si on me donne que est régulier, comment puis - je prouver que les éléments suivants L ' est régulière, aussi?LLLL′L′L' L′: = { W ∈ L : u v...
Dans ma classe, un étudiant a demandé si tous les automates finis pouvaient être dessinés sans croiser les bords (il semble que tous mes exemples l'ont fait). Bien sûr, la réponse est négative, l'automate évident pour la langue {x∈{a,b}∗∣#a(x)+2#b(x)≡0mod5}{x∈{a,b}∗∣#a(x)+2#b(x)≡0mod5}\{\;...
Je lisais sur Iota et Jot et j'ai trouvé cette section déroutante: Contrairement à Iota, où l'arbre syntaxique d'une chaîne peut se ramifier à gauche ou à droite, la syntaxe Jot est uniformément ramifiée à gauche. Par conséquent, Iota est strictement sans contexte, mais Jot est un langage régulier....
Je viens de terminer le premier chapitre de l' introduction à la théorie du calcul de Michael Sipser qui explique les bases des automates finis. Il définit un langage régulier comme tout ce qui peut être décrit par un automate fini. Mais je n'ai pas pu trouver où il explique pourquoi une langue...
Pour un langage régulier , soit le nombre de mots dans de longueur . En utilisant la forme canonique de Jordan (appliquée à la matrice de transition non annotée de certains DFA pour ), on peut montrer que pour un assez grand , où sont des polynômes complexes et sont des "valeurs propres" complexes....
Voici une conjecture pour les expressions régulières: Pour l'expression régulière , laissez la longueurêtre le nombre de symboles qu'il contient, en ignorant les parenthèses et les opérateurs. Par exemple| R | | 0 ∪ 1 | = | ( 0 ∪ 1 ) ∗ | = 2RRR| R ||R||R|| 0∪1 | = |( 0 ∪ 1 )∗| =2|0∪1|=|(0∪1)∗|=2|0...
Nous savons que les DFA sont équivalents aux NFA en termes de pouvoir d'expressivité; il existe également un algorithme connu pour convertir les NFA en DFA (malheureusement je connais maintenant l'inventeur de cet algorithme), qui dans le pire des cas nous donne états, si notre NFA avait états....
Wikipedia a la définition suivante du lemme de pompage pour les langages réguliers ... Soit LLL une langue régulière. Il existe alors un entier ppp ≥ 1 dépendant uniquement de LLL tel que chaque chaîne www dans LLL de longueur au moins ppp ( ppp est appelé la "longueur de pompage") puisse s'écrire...
Laisser L={an∣∃p≥n p, p+2 are prime}.L={an∣∃p≥n p, p+2 are prime}.\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}. est-il régulier?LLL Cette question paraissait suspecte au premier coup d'œil et je me suis rendu compte qu'elle était liée à la conjecture principale jumelle ....
Je suis coincé sur la question suivante: "Les langages réguliers sont précisément ceux acceptés par les automates finis. Étant donné ce fait, montrez que si le langage est accepté par un automate fini, alors est également accepté par un certain fini; compose de tous les mots de inversé....
J'essaie d'utiliser le lemme de pompage pour prouver que n'est pas régulier.L = { ( 01 )m2m∣ m ≥ 0 }L={(01)m2m∣m≥0}L = \{(01)^m 2^m \mid m \ge0\} Voici ce que j'ai jusqu'à présent: supposons que est régulier et que soit la longueur de pompage, donc . Considérons toute décomposition de pompage telle...
Réglage: expressions régulières avec références arrières langue unaire (alphabet à 1 symbole) Le problème suivant est-il décidable dans ce paramètre: Étant donné une expression régulière avec des références arrières, définit-elle un langage régulier? Par exemple, (aa+)\1définit une langue...
Il y a beaucoup (et je veux dire beaucoup) de langues dénombrables qui sont décidables par Turing. Est-ce qu'une langue innombrable peut être décidable de
Selon Wikipedia , pour tout langage régulier LLL il existe des constantes λ1,…,λkλ1,…,λk\lambda_1,\ldots,\lambda_k et des polynômes p1(x),…,pk(x)p1(x),…,pk(x)p_1(x),\ldots,p_k(x) tels que pour tout nnn le nombre sL(n)sL(n)s_L(n) de mots de longueur nnn dans LLL satisfait l'équation...
Je ne suis pas certain de l'utilisation des expressions langage "infini" ou langage "fini" en théorie informatique. Je pense que la racine du problème est qu'un langage comme est infini dans le sens où il peut générer un nombre infini (mais dénombrable) de chaînes. Pourtant, il peut encore être...
On dit que l'intersection d'un langage L sans contexte avec un langage M normal est toujours sans contexte. J'ai compris la preuve de la construction de produits croisés, mais je ne comprends toujours pas pourquoi elle est sans contexte mais pas régulière. Le langage généré par une telle...
Notez qu'il s'agit d'une question liée à l'étude dans un cours de CS dans une université, ce n'est PAS des devoirs et peut être trouvé ici sous l'examen d'automne 20112. Voici les deux questions que je regarde d'un examen passé. Ils semblent être liés, le premier: Laisser FINITECFG={<G>∣G is...
Étant donné les langues AAA et BBB , disons que leur concaténation ABABAB est sans ambiguïté si pour tous les mots w∈ABw∈ABw \in AB , il y a exactement une décomposition w=abw=abw = ab avec a∈Aa∈Aa \in A et b∈Bb∈Bb \in B , et ambiguë sinon. (Je ne sais pas s'il existe un terme établi pour cette...
Si j'ai une grammaire de type 3, elle peut être représentée sur un automate déroulant (sans faire aucune opération sur la pile) afin que je puisse représenter des expressions régulières en utilisant des langages sans contexte. Mais puis-je savoir si une grammaire de type 3 est , L L ( 1 ) , S L R (...
Existe-t-il une caractérisation algébrique du nombre de mots d'une longueur donnée dans une langue régulière? Wikipédia énonce un résultat quelque peu imprécis: Pour tout langage régulier il existe des constantes et des polynômes tels que pour tout le nombre de les mots de longueur dans satisfont à...