Utiliser le lemme de pompage pour prouver le langage

J'essaie d'utiliser le lemme de pompage pour prouver que n'est pas régulier.$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 que et .p w = ( 01 ) p 2 p w = x y z | y | > 0 | x y | ≤ $L$$p$$w = (01)^p 2^p$$w = xyz$$|y| >0$$|xy| \le p$

Je ne sais pas quoi faire ensuite.

Suis-je sur la bonne voie? Ou suis-je loin?

Astuce: Vous devez considérer à quoi ressemblent toutes les décompositions , donc quelles sont toutes les choses possibles x , y et z peuvent être données que x y z = ( 01 ) p 2 p . Ensuite, vous pompez chacun et voyez si vous obtenez une contradiction, qui sera un mot qui n'est pas dans votre langue. Chaque cas doit conduire à une contradiction, qui serait alors une contradiction du lemme de pompage. Voila! La langue ne serait pas régulière.$w=xyz$$x$$y$$z$$xyz=(01)^p2^p$

Bien sûr, vous devez étudier les détails et considérer toutes les séparations possibles.

Vous avez une décomposition et une contrainte de longueur | x y | ≤ p . Qu'est-ce que cela dit sur la façon dont x , y et z peuvent s'intégrer dans la décomposition? En particulier, le lemme de pompage vous permet de répéter y , votre objectif est donc de trouver un moyen de répéter y plusieurs fois (ou de supprimer y , parfois c'est plus simple) perturbera irrémédiablement le modèle qui définit la langue.$xyz = (01)^p 2^p$$|xy| \le p$$x$$y$$z$$y$$y$$y$

Il y a une limite évidente dans le motif: la première partie contient des répétitions de , la deuxième partie n'en contient que 2 . La chose intéressante est où y tombe. Est - y toujours contenu dans une de ces parties, ou peut - il enjamber les deux?$01$$2$$y$$y$

Depuis , x y est entièrement contenu dans la partie ( 01 ) p , et z contient tous les 2 . Donc, si vous répétez y une fois de plus, vous obtenez une première partie plus longue, mais la partie 2 p reste la même. En d'autres termes, x y y z se termine par exactement p lettres 2 . Pour terminer l'épreuve correctement, montrez que x y y z contient trop de lettres 0 et $|xy| \le p$$xy$$(01)^p$$z$$2$$y$$2^p$$xyyz$$p$$2$$xyyz$$0$$1$ pour s'adapter à l'expression régulière.

Trois ans plus tard, nous allons prouver que avec Δ = { 0 , 1 , 2 } n'est pas régulier par contradiction en utilisant les propriétés de fermeture (un moyen plus rapide que d'utiliser le lemme de pompage ).$L = \{(01)^m 2^m \mid m \ge0\}$$\Delta=\{0,1,2\}$

On suppose d'abord que est régulier. Nous savons que les langages réguliers sont fermés par homomorphisme inverse.$L$

Considérons l'homomorphisme avec:$h:\Sigma^* \rightarrow \Delta^*$

$\Sigma = \{a,b\}$

$h(a)= 01$

$h(b)= 2$

L'homomorphisme inverse de est:$L$

$h^{-1}(L)= \{a^nb^n| n\geq 0 \} = L'$

Cela génère une contradiction car est un exemple canonique d'un langage irrégulier donc L ne peut pas être régulier.$L'$$L$

Je vais donner une non-réponse à cette question, car ce n'est pas exactement le lemme de pompage, mais peut-être éclaircit ce qu'est l'idée du lemme de pompage. Voici un fait de base sur les automates à états finis déterministes, qui est l'essence du théorème de Myhill-Nerode: Si deux chaînes et b conduisent le FSA au même état, alors pour tout c , les deux a c et b c sont accepté, ni l'un ni l'autre.$a$$b$$c$$ac$$bc$

Revenons à votre problème, supposons qu'un automate déterministe pour votre langue ait états. Alors au moins deux de ( 01 ) 1 , ( 01 ) 2 , … , ( 01 ) n + 1 , disons ( 01 ) p et ( 01 ) q avec p ≠ q , conduisent l'automate dans le même état (c'est le principe du pigeonnier). Selon le fait, alors soit les deux ( 01 ) p 2 p et$n$$(01)^1$$(01)^2$$\ldots$$(01)^{n+1}$$(01)^p$$(01)^q$$p\neq q$$(01)^p2^p$ sont dans L ou aucun ne l'est, ce qui est une contradiction.$(01)^q2^p$$L$