Sistemas de informação

Ensino de linguagens formais e autômatos em cursos superiores de computação
Marcus Vinícius Midena Ramos
Revista de Computação e Tecnologia da PUC-SP — Departamento de Computação/FCET/PUC-SP ISSN 2176-7998
Hierarquia de Chomsky
O corpo de conhecimento contido na área de linguagens formais e autômatos é derivado de duas sub-áreas de conhecimento que eram consideradas de forma independente uma da outra até adécada de 1960: linguagens formais, de um lado, e teoria de autômatos, de outro. Foi a partir das pesquisas efetuadas e dos resultados obtidos nessa década que se pôde estabelecer uma relação mais direta entre tais sub-áreas, as quais foram, a partir de então, combinadas numa única grande área de conhecimento e são, nos dias de hoje, consideradas como sendo praticamente indissociáveis uma da outra.
A sub-área linguagens formais trata da caracterização, classificação, formalização e estudo das propriedades das linguagens estruturadas em frases.
O marco inicial dessa sub-área é o trabalho de Chomsky, um matemático e linguísta que, em meados da década de 1950, pesquisava a formalização gramatical de linguagens naturais. Apesar do seu insucesso no cumprimento desse objetivo, ele apresentou uma classificação das linguagens estruturadas em frases, organizada em níveis de complexidade crescente, que se tornaria referência fundamental para o estudo das linguagens formais. Tal classificação passou a ser conhecida como Hierarquia de Chomsky [2].
Partindo-se da classe de linguagens mais “simples” em direção à classe de linguagens mais “complexa” (os termos “simples” e “complexa” referem-se aos diversos aspectos das classes de linguagens consideradas, mas costumam englobar propriedades estruturais, aspectos de formalização sintática, custo do reconhecimento e grau de dificuldade na demonstração de certas propriedades), a Hierarquia de Chomsky contempla: a classe das linguagens regulares (ou tipo 3); a classe das linguagens livres de contexto (ou tipo 2); a classe das