Linguagens Formais e Autômatos

Linguagens Formais e Autômatos

1

LINGUAGENS FORMAIS E AUTÔMATOS
Linguagens Formais
Noam Chomsky definiu as linguagens naturais podem ser classificadas em classes de linguagens. Segundo a Hierarquia de Chomsky, as linguagens podem ser divididas em quatro classes, sendo elas:
Regulares ou Tipo 3;
Livres de Contexto ou Tipo 2;
Sensíveis ao Contexto ou Tipo 1;
Recursivamente Enumeráveis ou Tipo 0.

LR

LLC

LSC

LRE

Linguagens Regulares
As linguagens regulares podem ser estudadas abordando os seguintes formalismos. Autômato Finito.
Trata se de um reconhecedor da linguagem. Este se resume em um sistema de estados finitos;
Expressão Regular.
Trata se de um gerador da linguagem, pois é possível através desta construir todas as palavras da linguagem.
Gramática Regular.
Trata se de um gerador da linguagem, a qual é representada por regras gramaticais restritas.

Autômatos Finitos
Autômatos Finitos Deterministicos
Autômatos Finitos Não Deterministicos

Linguagens Formais e Autômatos

2

Expressões Regulares
Toda linguagem regular pode ser descrita por uma expressão simples, denominada Expressão Regular (ER). Trata-se de um formalismo gerador, pois expressa como construir (gerar) as palavras da linguagem. Uma ER é definida recursivamente a partir de conjuntos (linguagens) básicas e operação de concatenação e união.
Regras de Formação de ER
Uma expressão regular r, sobre um conjunto de símbolos T, representa uma linguagem L(r), a qual pode ser definida indutivamente a partir de expressões básicas, como segue:
1.
2.
3.
4.

Notações
|
()
*
+
Σ*

∅ representa a linguagem vazia (conjunto contendo zero palavras);
{ε} representa a linguagem cuja única palavra é a palavra vazia;
{x | x ∈ T} representa a linguagem cuja única palavra é x; se r1 e r2 são expressões regulares que definem as linguagens L(r1) e
L(r2), tem-se que:
a. r1|r2 é a linguagem cujas palavras constituem o conjunto L(r1) ∪
L(r2). Alguns