Saltar para o conteúdo

Gramática regular

Ourige: Biquipédia, la anciclopédia lhibre.

An Teorie de la cumputaçon las Gramáticas regulares tamien coincida cumo Tipo 3 de la Hierarquia de Chomsky, ye ua restriçon subre la forma de las porduçones, puode-se criar ua nuoba classe de gramáticas de grande amportança ne l studo de ls cumpiladores por possuíren propiadades adequadas pa l'oubtençon de reconhecedores simples. Que tamien puoden ser chamada de Spresson regular.


Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky
Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito