Como sentir intuitivamente que um idioma é regular

Dado um idioma , como posso dizer diretamente, sem examinar as regras de produção, que esse idioma não é regular?$L= \{a^n b^n c^n\}$

Eu poderia usar o lema de bombeamento, mas alguns caras estão dizendo apenas olhando para a gramática que essa não é regular. Como isso é possível?

A principal propriedade dos DFA / NFA é a falta de memória ilimitada. Se você olhar para um idioma e o único algoritmo (que mais tarde deve ser traduzido em um autômato finito), poderá pensar em requerer essa propriedade, ou seja, sentirá que qualquer algoritmo que o reconheça precisará se lembrar de um grande número arbitrário de coisas (como no seu exemplo), esse idioma provavelmente não é regular.$n$

Obviamente, você deve sempre lembrar que a intuição matemática pode estar errada, e a única maneira de ter certeza de sua intuição é prová-la.

EDIT: Vou responder a última pergunta nos comentários aqui, por falta de espaço.

vocês estão falando sobre memória ilimitada, o que você quer dizer é a razão pela qual ela não é regular. mas um ^ nb ^ m também pode ter memória ilimitada, se eu quiser, não é? isso ainda não está me dando paz.

O problema não é o tamanho das palavras (geralmente você encontrará idiomas regulares infinitos, porque todos os idiomas finitos são regulares e isso é bastante chato), mas o quanto o DFA precisa se lembrar.
Na exemplo, não há nenhuma necessidade de se lembrar m , n . O algorihm só precisa ter certeza de que é positivo e que a palavra está ordenada corretamente. Essa é uma lista finita e cada um dos itens da lista requer uma quantidade constante de memória. Compare isso com a n b n , para o qual é necessário um alogritmo simples para lembrar que o número de a é igual ao número de $a^mb^n$$m,n$
$a^nb^n$$a$$b$'s. Isso exigirá memória ilimitada. Quando olho para uma linguagem e vejo que qualquer algoritmo em que consigo pensar precisa de memória ilimitada, minha intuição de que a linguagem não é regular fica mais forte. Se não conseguir encontrar um algoritmo "inteligente" (que exija uma quantidade constante de memória) em um período de tempo razoável (quanto tempo é razoável depende de você), tentarei provar que o idioma não é regular.
Espero que isso torne um pouco mais claro.

Eu poderia usar o lema de bombeamento

Exatamente. Depois de usar o lema de bombeamento ou qualquer outra técnica algumas (dezenas), você começará a ver os padrões nos idiomas que os proíbem de serem regulares. é muito básico que você provavelmente já domina. Portanto, isso também é uma questão de experiência, não apenas intuição.$a^n\dots b^n$

Uma boa maneira de testar sua intuição é olhar para estes idiomas:

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\}^*\}$

Quais são livres de contexto?

Você pode decidir se um idioma é regular usando cálculos bastante diretos, em vez de fazer uma prova completa. Você simplesmente precisa aplicar um critério muito poderoso: um idioma é regular se, e somente se, possui muitos quocientes finitos.

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