Comment sentir intuitivement qu'une langue est régulière

Étant donné un langage , comment dire directement, sans regarder les règles de production, que ce langage n'est pas régulier?$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-ce possible?

La principale propriété des DFA / NFA est le manque de mémoire illimitée. Si vous regardez une langue et le seul algorithme (qui devrait plus tard être traduit en un automate fini) auquel vous pouvez penser requiert cette propriété, c'est-à-dire que vous pensez que tout algorithme qui le reconnaîtra devra se souvenir d'un nombre arbitraire de choses (comme dans votre exemple) alors cette langue n'est probablement pas régulière.$n$

Bien sûr, vous devez toujours vous rappeler que l'intuition mathématique peut être erronée, et la seule façon d'être sûr de votre intuition est de le prouver.

EDIT: Je vais répondre à la dernière question dans les commentaires ici, à cause du manque d'espace.

vous parlez de mémoire illimitée, ce que vous voulez dire, c'est la raison pour laquelle ce n'est pas régulier. mais un ^ nb ^ m peut aussi avoir une mémoire illimitée si je veux, n'est-ce pas? cela ne me donne toujours pas de paix.

Le problème n'est pas la taille des mots (vous rencontrerez généralement des langages réguliers infinis, car chaque langue finie est régulière, et c'est assez ennuyeux), mais combien le DFA doit se souvenir.
Dans l' , il n'est pas nécessaire de se souvenir de m , n . L'algorihm a juste besoin de s'assurer qu'ils sont positifs et que le mot est correctement ordonné. Il s'agit d'une liste finie et chacun des éléments de la liste nécessite une quantité constante de mémoire. Comparez cela à un n b n , pour lequel un simple alogrithme est nécessaire pour se rappeler que le nombre de a est égal au nombre de$a^mb^n$$m,n$
$a^nb^n$$a$$b$'s. Cela nécessitera une mémoire illimitée. Quand je regarde un langage et que tout algorithme auquel je pense peut avoir besoin d'une mémoire illimitée, mon intuition que le langage n'est pas régulier se renforce. Si je ne trouve pas d'algorithme "intelligent" (qui nécessite une quantité de mémoire constante) dans un laps de temps raisonnable (combien de temps est à vous), j'essaierai de prouver que la langue n'est pas régulière.
J'espère que cela le rend un peu plus clair.

Je pourrais utiliser le pompage de la lemme

Exactement. Après avoir utilisé le lemme de pompage ou l'une des autres techniques plusieurs fois (des dizaines), vous commencerez à voir$a^n\dots b^n$

Un bon moyen de tester votre intuition est de regarder ces langues:

1. $\quad \displaystyle \{xyyz \mid x,y,z \in \{a,b\}^+\}$
2. $\quad \displaystyle \{xyyz \mid x,y,z \in \{a,b\}^*\}$
3. $\quad \displaystyle \{xyyz \mid x,y,z \in \{a,b,c\}^+\}$
4. $\quad \displaystyle \{xyyz \mid x,y,z \in \{a,b,c\}^*\}$

Quels sont sans contexte?

Vous pouvez réellement décider si une langue est régulière en utilisant des calculs assez simples, plutôt que de faire une preuve complète. Il suffit d'appliquer un critère très puissant: une langue est régulière si et seulement si elle a un nombre fini de quotients.

$L$$x$$x\setminus L$$w$$xw \in L$$L=\{a^nb^n\}$$a\setminus L= \{a^{n-1} b^n | n\ge 1 \}$$b \setminus L=\emptyset$$a^k \setminus L = \{a^{n-k}b^n | n \ge k \}$$L$

$D$$D$$S$$a$$a\setminus L$$D$$S$