Questions marquées «regular-languages»

Je lis actuellement le livre Introduction à la théorie du calcul (2e ou 3e éd.) De Michael Sipser , et je suis tombé sur une question du chapitre 1 - Langues régulières , à savoir lorsque l'auteur présente l'idée de preuve du théorème 1.49 - "La classe des langues régulières est fermée sous...

Étant donné un DFA, A, soit L (A) le nombre de mots que A accepte. Je pense qu'il est facile de calculer L (A): Traduisez l'encodage de A en une expression régulière. Si l'étoile Kleene apparaît n'importe où dans l'expression - le langage est infini. Sinon: Parcourez et comptez toutes les...

J'ai du mal à déterminer si tous les nombres carrés (1, 4, 9, 16, ...) écrits sous forme binaire (1, 100, 1001, ...) sont une langue régulière. Après quelques tentatives pour trouver un modèle commun de ces nombres, j'ai découvert que pour tout nombre carré , est égal à 0 ou 1, et je suis donc en...

Considérez la séquence . Il semble "régulier" d'une manière qui, par exemple, ne l'est pas.s1=(1,0,1,0,…)s1=(1,0,1,0,…)s_1 = (1, 0, 1, 0,\dots)s2=(1,2,3,4,…)s2=(1,2,3,4,…)s_2 = (1, 2, 3, 4,\dots) Je ne sais pas comment formaliser cette intuition cependant. Une chose qui me saute aux yeux est que...

Dans notre cours sur les concepts du langage de programmation, notre instructeur a affirmé qu'il est acceptable qu'un état final mène à un autre état dans un diagramme à états finis. Mais cela semble être un concept fondamentalement contradictoire. Parce qu'un état final par définition est un état...

C'est quelque chose que je n'ai pas trouvé - mais j'ai toujours trouvé intéressant que le lemme de pompage soit juste un lemme (d'autant plus qu'il a le même nom pour les langues régulières, les langues sans contexte, etc ...) Qu'est-ce qu'un

Je travaille sur un analyseur pour un langage de style C, et pour cet analyseur, j'ai besoin de l'expression régulière qui correspond au style C / ** / commentaires. Maintenant, j'ai trouvé cette expression sur le web: /\*([^\*]*\*+[^\*/])*([^\*]*\*+|[^\*]*\*/ Cependant, comme vous pouvez le voir,...

En classe, notre professeur nous a montré 3 méthodes pour prouver la non-régularité: Théorème de Myhill – Nerode Pompage du lemme pour les langues régulières Preuve de non-régularité, basée sur la complexité de Kolmogorov Maintenant les deux premiers, le théorème de Myhill-Nerode et le lemme de...

J'ai en quelques jours un examen et j'ai des problèmes pour résoudre cette tâche. Laisser LLL être une langue régulière sur l'alphabet ΣΣ\Sigma. Nous avons l'opération cycle(L)={xy∣x,y∈Σ∗ and yx∈L}cycle⁡(L)={xy∣x,y∈Σ∗ and yx∈L}\operatorname{cycle}(L) = \{ xy \mid x,y\in \Sigma^* \text{ and } yx\in...

Ma question porte essentiellement sur trois langues A, B et L, où L est A et B concaténés ensemble et B se révèle non régulier, est-il possible de trouver un A qui rend L

Nous avons deux langues: . Nous savons que est un langage régulier, donc ma question est de savoir si est régulier vers?L1,L2L1,L2L_1,L_2L1L2L1L2L_1L_2L2L1L2L1L_2L_1 J'essaie de trouver un moyen de le prouver ... Je ne peux bien sûr pas supposer que L1,L2L1,L2L_1,L_2sont réguliers ... Je cherche...

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...

Donc, je me gratte la tête sur ce problème depuis quelques jours maintenant. Étant donné une certaine langueUNEAA et BBB c'est régulier, montrer que la langue LLL qui se compose de toutes les chaînes UNEAA dont la longueur est égale à une chaîne BBB est une langue régulière. Sous forme d'équation:...

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...

Laisser L = {unen∣ n ≥ 0 }L={an∣n≥0}L = \{a^n \mid n \ge 0\}, où une0= ϵa0=ϵa^0 = \epsilon et unen=unen - 1unean=an−1aa^n = a^{n-1}a pour tous n ≥ 1n≥1n \ge 1. Donc LLL se compose de séquences de uneaa de toutes les longueurs, y compris une séquence de longueur 000. LaisserL2L2L_2 être un...

Comme je l'ai étudié, décider de la régularité des langages sans contexte est indécidable. Cependant, nous pouvons tester la régularité en utilisant le théorème de Myhill – Nerode qui fournit une condition nécessaire et suffisante. Le problème devrait donc être décidable. Où est mon...

Laisser LLLêtre une langue régulière. Est la langueL2={y:∃x,z  s.t.|x|=|z| and xyz∈L}L2={y:∃x,z  s.t.|x|=|z| and xyz∈L}L_2 = \{y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \in L \} ordinaire? Je sais que c'est très similaire à la question ici , mais le hic, c'est que ce n'est pas une simple sous-chaîne...

Laisser LLLêtre une langue régulière. Prouve-le: L+−−={w:∃u|u|=2|w|∧wu∈L}L+−−={w:∃u|u|=2|w|∧wu∈L}L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\} L++−={w:∃u2|u|=|w|∧wu∈L}L++−={w:∃u2|u|=|w|∧wu∈L}L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}...