Propriétés nécessaires des langages formels dans certaines classes qui reposent sur la fermeture contre la répétition de certains sous-mots. Assurez-vous que votre question n'est pas couverte en appliquant les techniques de https://cs.stackexchange.com/q/1031/755.
Le contexte linguistique suivant est-il libre? L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} Comme indiqué par sdcvvc, un mot dans cette langue peut également être...
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...
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...
Donc, fondamentalement, L satisfait aux conditions du lemme de pompage pour les CFL mais n'est pas un CFL (ce qui est possible selon la définition du
Je me demandais quand les langues contenant le même nombre d'instances de deux sous-chaînes seraient régulières. Je sais que le langage contenant un nombre égal de 1 et de 0 n'est pas régulier, mais est un langage tel que , où = nombre moyen d'instances de la sous-chaîne "001" est égal au nombre...
J'ai la langue suivante { 0je1j2k∣ 0 ≤ i ≤ j ≤ k }{0i1j2k∣0≤i≤j≤k}\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\} J'essaie de déterminer dans quelle classe de langue Chomsky il s'intègre. Je peux voir comment cela pourrait être fait en utilisant une grammaire contextuelle, donc je sais qu'elle...
Le lemme de pompage pour les langues régulières peut être utilisé pour prouver que certaines langues ne sont pas régulières, et le lemme de pompage pour les langues sans contexte (avec le lemme d'Ogden) peut être utilisé pour prouver que certaines langues ne le sont pas. Existe-t-il un lemme de...
Décrivez une langue régulière qui ne peut être acceptée par aucun DFA qui ne comporte que trois états. Je ne sais pas trop par où commencer et je me demandais si quelqu'un pourrait me donner quelques conseils ou astuces. Je comprends que le lemme de pompage peut être utilisé pour prouver qu'une...
Étant donné un langage , comment dire directement, sans regarder les règles de production, que ce langage n'est pas régulier?L={anbncn}L={anbncn} L= \{a^n b^n c^n\} Je pourrais utiliser le lemme de pompage mais certains gars disent juste en regardant la grammaire que ce n'est pas normal. Comment...
Est la langue L = { a , b}∗∖ { (unenbn)n∣ n ≥ 1 }L={a,b}∗∖{(anbn)n∣n≥1}L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \} sans contexte? Je crois que la réponse est que ce n'est pas une LFC, mais je ne peux pas le prouver par le lemme d'Ogden ou le lemme de
Montre CA L={an2|n≥0}L={an2|n≥0}L=\{a^{n^2} | n \geq 0\} n'est pas régulier Salut les gars. Je prends un cours de CS et ce truc est vraiment nouveau pour moi, alors soyez indulgent avec moi. J'ai essayé de voir si j'obtenais une contradiction en utilisant le lemme de pompage pour les langues...
J'ai deux questions: Je considère la langue suivante L1= { w ∈ { 0 , 1}∗∣ ∄ u ∈ { 0 , 1}∗: w = uuR} .L1={w∈{0,1}∗∣∄u∈{0,1}∗:w=uuR}.L_1= \{ w\in \{0,1\}^* \mid \not \exists u\in \{0,1\}^* \colon w= uu^R\}. En d'autres termes wwwn'est pas palindrome de même longueur. J'ai prouvé que ce langage n'est...
Est la langue L={0n1m∣n and m are co-prime}L={0n1m∣n and m are co-prime} L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\} sans contexte? Je suppose que ce n'est pas sans contexte car il semble trop compliqué pour un PDA de décider si 2 nombres sont co-amorcés ou non. J'ai essayé...
Une propriété de «pompage» (des mots d'une certaine longueur impliquent l'existence de boucles dans le mécanisme de définition de la langue) est connue pour exister pour les langues régulières et sans contexte et quelques autres (généralement utilisées pour réfuter l'appartenance d'une langue à une...