Como sentir intuitivamente que um idioma é regular

9

Dado um idioma , como posso dizer diretamente, sem examinar as regras de produção, que esse idioma não é regular?L={anbncn}

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?

doniyor
fonte
11
Qualquer um pode olhar para qualquer idioma e apenas dizer que não é regular. Não tenho certeza se a intuição, por si só, está em jogo tanto quanto a experiência. Essa é uma linguagem bastante simples (apesar de não ser regular) e inevitavelmente encontrada no estudo de línguas formais. Depois que você é informado de que não é regular e provou que não é regular usando qualquer técnica de prova válida, normalmente você não precisa de uma prova para convencer outras pessoas, porque todas elas provaram isso quando foram apresentadas ao sujeito.
Patrick87
sim, mas às vezes em palestras que basta seguir mostra alguns matemática seca, mas eles realmente não têm explicações intuitivas com exemplos reais simples
doniyor
Esqueça . Você já sentiu que um n b n não é regular? anbncnanbn
precisa
2
Olhar para uma gramática e proclamar porque a gramática não é regular, o idioma não é regular é uma falácia. Existem muitas gramáticas não regulares para idiomas regulares. Cuidado! Dito isto, é fácil decidir se uma gramática é regular; basta verificar as produções.
Raphael

Respostas:

11

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 bambnm,n
anbnab'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.

Boris Trayvas
fonte
obrigado, provas matemáticas trazem a intuição, mas veja esta regra de produção: S -> ab | aSb. isto é para um ^ nb ^ n que diz que também não é regular. mas a ^ mb ^ n é regular com m, n> = 1. por que é isso? estes são realmente da mesma forma, certo? Eu não entendo a diferença entre estas duas línguas
doniyor
11
Para a ^ nb ^ n, você precisa acompanhar duas coisas: primeiro, que o número de a seja igual ao número de b's (essa é a parte impossível para os DFAs) e, depois, que nenhum 'b' é seguido por um 'a ' Para um ^ mb ^ n, você não se importa com o valor de m, n. Você só se importa que haja pelo menos um 'a' e pelo menos um 'b' e que nenhum 'b' seja seguido por um 'a'. Informalmente, você precisa se lembrar apenas de 3 coisas.
Boris Trayvas
oh ok, agora eu entendi.
doniyor
então a ordem também é crucial, certo? como o aabbcc aceito, mas não o aabcbc apenas porque o pedido não está correto. direita?
doniyor
11
"A principal propriedade das linguagens regulares é a falta de memória ilimitada". - Eu sei o que você quer dizer, mas essa frase não faz nenhum sentido. "você acha que qualquer algoritmo que o reconheça precisará se lembrar de um grande número arbitrário de coisas" - Essa é realmente a única intuição que eu também conheço, mas seu tipo é muito, muito perigoso; veja aqui .
Raphael
5

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

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

  1. {xyyzx,y,z{a,b}+}
  2. {xyyzx,y,z{a,b}}
  3. {xyyzx,y,z{a,b,c}+}
  4. {xyyzx,y,z{a,b,c}}

Quais são livres de contexto?

Rafael
fonte
11
Se alguém conhece exemplos igualmente legais para a fronteira de idiomas regulares, diga-o. Por favor, não estrague a resposta nos comentários.
Raphael
Raphael - ótimo trabalho! obrigado por dar exemplos e por me testar explicitamente.
doniyor
@doniyor vamos continuar esta discussão no chat
Raphael
4

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.

LxxLwxwLL={anbn}aL={an1bn|n1}bL=akL={ankbn|nk}L

DDSaaLDS

James Koppel
fonte
b \ L significa: se eu dividir o L por b, ficarei vazio definido ?. é porque eu realmente tenho que começar a ler a palavra do começo? e não por trás?
doniyor
11
bL=L/b
11
Aqui está um baralho bom slides que explica quocientes, e como construir DFAs deles: cs.cmu.edu/~cdm/pdf/Minimization.pdf
James Koppel
oh ok, muito obrigado. agora eu tenho um pouco. mmm ... deixe-me estudar este novo por um tempo embora ...
doniyor