Buscar

Linguagens Formais e Autômatos 2

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 13 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 13 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 13 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Linguagens Formais e Autômatos – 1º Semestre de 2015
3 - Tipos de Gramáticas Segundo a Hierarquia de Chomsky
Uma hierarquia de linguagens de programação baseada no aumento da independência da 
máquina, possui no seu topo as linguagens orientadas a problemas, ou seja, linguagens que possuem 
um enfoque voltado a um problema específico e que refletem sua estrutura e sua terminologia. 
Em seguida, vem a classe de linguagens de alto-nível, a classe mais importante e mais 
utilizada, composta por estruturas de controle e decisão. Estas linguagens ainda estão próximas das 
linguagens naturais. Abaixo, estão as linguagens de montagem, que basicamente atribuem 
mnemônicos as instruções de máquinas da última classe de linguagem, as linguagens de baixo-
nível, ou seja, as linguagens nativas dos computadores onde cada instrução é representada por um 
valor numérico.
Das classes da hierarquia baseadas na independência de máquina, vamos nos ater a classe de 
linguagens de alto-nível, uma vez que é no escopo destas linguagens que os compiladores atuam. 
De modo geral, pode-se definir as linguagens de alto-nível, as quais de agora em diante serão 
chamadas simplesmente de linguagens, como uma coleção de cadeia de símbolos, de comprimento 
finito. Estas cadeias são denominadas sentenças da linguagem e são formadas pela justaposição de 
elementos individuais, os símbolos ou átomos da linguagem.
A teoria de Chomsky nos mostra que existem quatro classes de gramáticas que são capazes 
de gerar quatro classes de linguagens correspondentes. As quatro classes de gramáticas são:
· Gramáticas Irrestritas;
· Gramáticas Sensíveis ao Contexto;
· Gramáticas Livres de Contexto;
· Gramáticas Lineares à Direita (esquerda).
Conseguimos atingir estas quatro classes de gramáticas devido às restrições impostas pelas 
produções desta gramática, conseqüentemente, as linguagens formadas por estas gramáticas 
também são atingidas. Por este motivo é que dizemos que para cada tipo de gramática existe uma 
linguagem correspondente.
3.1 - Gramáticas Irrestritas
As Gramáticas Irrestritas são as gramáticas formadas sem a imposição de qualquer tipo de 
9
 Linguagens Formais e Autômatos – 1º Semestre de 2015
restrição por parte das produções, desta forma ela não possui limitação, gerando Linguagem 
estruturada em frases. 
Como as gramáticas irrestritas não possuem limitação elas compreendem todas as 
linguagens que podem se definir através de mecanismos generativos, ou seja, mecanismos que 
possam ser gerados por estas gramáticas.
Segundo a Hierarquia de Chomsky este tipo de gramática é classificado como gramática do 
tipo 0 e as linguagens que são formadas por este tipo de gramáticas também são 
correspondentemente linguagens do tipo 0.
Exemplo:
G=({A,B,C},{a,b},{A→BC, BC→CB, CB→b, B→b, BC→a },A)
3.2 - Gramáticas Sensíveis ao Contexto
As Gramáticas Sensíveis ao Contexto são as gramáticas formadas pela imposição de 
restrição por parte das produções, desta forma as regras de substituições impostas não podem 
reduzir a forma sentencial à qual a substituição é aplicada, ou seja, a cadeia posterior à substituição 
tem que possuir um número igual ou maior de símbolos.
Segundo a Hierarquia de Chomsky este tipo de gramática é classificado como gramática do 
tipo 1 e as linguagens que são formadas por este tipo de gramáticas também são 
correspondentemente linguagens do tipo 1 (Linguagem sensível ao contexto). Desta forma, as 
linguagens do tipo 1 podem ser geradas através de gramáticas do tipo 0 (Gramáticas Irrestritas), 
embora o inverso não seja possível.
Exemplo:
G = ({A,B,C},{a,b},{A→AB, AB→AC, C→abA, B→b,AB→bb, A→a},A)
3.3 - Gramáticas Livres de Contexto
As Gramáticas Livres de Contexto são as gramáticas na qual questionamos o 
condicionamento das substituições, ou seja, levantamos o condicionamento das substituições 
imposta pelas regras definidas pela produção. Após este questionamento, eliminamos o 
condicionamento e aplicamos às produções uma restrição adicional, com a finalidade de assim 
restringirmos as produções das gramáticas deste tipo. Neste tipo de gramática, o lado esquerdo das 
10
 Linguagens Formais e Autômatos – 1º Semestre de 2015
produções possui apenas um não-terminal.
Segundo a Hierarquia de Chomsky este tipo de gramática é classificado como gramática do 
tipo 2 e as linguagens que são formadas por este tipo de gramáticas também são 
correspondentemente linguagens do tipo 2 (Linguagem livre de contexto). 
Desta forma, as linguagens do tipo 2 podem ser geradas através de gramáticas do tipo 1 
(Gramáticas Sensíveis ao Contexto) ou gramáticas do tipo 0 (Gramáticas Irrestritas).
Exemplo:
G=({S},{a,+,*,(,)},{S→S*S,S→S+S, S→(S), S→a}, S)
3.4 - Gramáticas Regulares 
As Gramáticas Regulares ou Lineares à Direita (Esquerda) são as gramáticas na qual as 
regras de produção admitem apenas a substituição de um não-terminal por uma cadeia de terminais, 
seguida ou não por um não-terminal único.
Segundo a Hierarquia de Chomsky este tipo de gramática é classificado como gramática do 
tipo 3 e as linguagens que são formadas por este tipo de gramáticas também são 
correspondentemente linguagens do tipo 3 (Linguagem Regular ou Linear à Direita). 
Desta forma, as linguagens do tipo 3 podem ser geradas através de gramáticas do tipo 2 
(Gramáticas Livres de Contexto), gramáticas do tipo 1 (Gramáticas Sensíveis ao Contexto) ou 
gramáticas do tipo 0 (Gramáticas Irrestritas).
Exemplo:
G=({S},{a,b},{S→aS, S→b }, S)
Obs.: Uma Gramática Linear à direita possui produções da forma A→wB ou A→w. Uma Linear à 
Esquerda, possui produções A→Bw ou A→w.
11
 Linguagens Formais e Autômatos – 1º Semestre de 2015
A figura a seguir, disponível em http://pt.wikipedia.org/wiki/Hierarquia_de_Chomsky, 
apresenta um resumo da Hieraquia de Chomsky.
3.5 - Expressões Regulares
Expressão Regular (ER) é uma maneira de descrever conjunto regulares de cadeias. Pode ser 
considerado também como um gerador, pois a partir da Expressão Regular pode-se gerar as palavras 
da linguagem.
Logo, uma Expressão Regular é um formalismo usado para definir o formato correto de uma 
cadeia de caracteres (palavras) da Linguagem sobre um alfabeto
Para a geração das cadeias são utilizadas as seguintes operações:
• Concatenção sucessiva (*)
• Concatenção ( . )
• União ( + )
A Concatenação Sucessiva tem precedência sobre a concatenação, a qual tem precedência 
sobre a união.
Considere o alfabeto V = {a, b}. Nele podemos ter as seguintes relações:
12
 Linguagens Formais e Autômatos – 1º Semestre de 2015
Expressão Regular Linguagem Representada
aa somente a palavra aa
ba* todas as palavras que iniciam por b, seguido por zero ou mais a
(a + b)* todas as palavras sobre o alfabeto { a, b }
(a + b)*aa(a + b)* todas as palavras contendo aa como subpalavra
a*ba*ba* todas as palavras contendo exatamente dois b
(a + b)*(aa + bb) todas as palavras que terminam com aa ou bb
13
 Linguagens Formais e Autômatos – 1º Semestre de 2015
4 – Linguagens Regulares
Segundo a Hierarquia de Chomsky, a Linguagem Regular trata-se de uma linguagem mais 
simples, sendo possível desenvolver algoritmos de reconhecimento ou de geração de pouca 
complexidade, grande eficiência e de fácil implementação.
O estudo das Linguagens Regulares ou tipo 3 (Hierarquia de Chomsky) pode ser visto 
através de vários formalismos:
• Operacional ou reconhecedor - uso dos autômatos finitos (determinístico, não 
determinístico)
• Axiomático ou gerador - gramática regular• Denotacional - expressão regular
4.1 - Reconhecedores
Ao contrário das gramáticas, que geram sentenças de uma linguagem, os reconhecedores são 
dispositivos de aceitação de cadeias, ou seja, realizam um teste de aceitação que determina se uma 
cadeia pertence ou não a linguagem. 
Pensando de maneira abstrata, podemos determinar os componentes da estrutura de um 
reconhecedor de cadeias. São eles:
• Uma cadeia de entrada; 
• Um cursor; e
• Uma máquina finita de estados.
A máquina finita de estados é o elemento central do funcionamento de um reconhecedor. 
Trata-se de uma máquina que possui a propriedade de realizar transições a partir de um elemento da 
cadeia de entrada. Dessa forma, o reconhecimento de uma cadeia transcorre fornecendo o elemento 
apontado pelo cursor à máquina finita de estados e esta respondendo com o estado resultante da 
transição. Vale comentar, que eventualmente os eventos ocorridos durante o reconhecimento são 
registrados em uma memória auxiliar. Em geral, essa memória e representada por uma pilha.
Antes de iniciar o processo de reconhecimento, é preciso levar o reconhecedor a uma 
 Linguagens Formais e Autômatos – 1º Semestre de 2015
configuração inicial. Para isso a máquina finita de estados deve também ser levada a sua 
configuração inicial, além disso o cursor deve apontar para o primeiro elemento da cadeia de 
entrada. Se a máquina finita de estados possuir memória auxiliar, esta deve conter um valor inicial 
específico e pré-determinado.
A cada instante do reconhecimento, podemos definir uma configuração ao reconhecedor 
como sendo uma tripla composta pelo estado corrente, pela posição do cursor na cadeia e conteúdo 
do texto de entrada, e valor da memória auxiliar. 
Uma cadeia submetida ao processo de reconhecimento é considerada reconhecida, e 
portanto, pertencente à linguagem definida pelo reconhecedor, se partindo da configuração inicial e 
passando por todos os elementos da cadeia, o reconhecedor realiza uma seqüência de movimentos 
que o leve a uma configuração final.
Todo reconhecedor deve ter no mínimo uma configuração final, de modo que os 
movimentos possíveis entre a configuração inicial e uma ou mais configurações finais descrevam as 
sentenças da linguagem considerada. Podemos então, definir uma configuração final como a 
situação em que o cursor aponta para uma posição após o último elemento da cadeia, então a 
máquina de estados encontra-se em um dos estados de aceitação e, se o reconhecedor trabalha com 
memória auxiliar, o conteúdo da memória satisfaz um critério preestabelecido.
4.1.1 – Formato de Reconhecedores
Para a representação de Reconhecedores são utilizadas três notações:
• Produções dos autômatos;
• Tabelas de Transição; e
• Diagramas de Estados.
a) Produções dos Autômatos:
Um autômato finito M sobre um alfabeto Σ é uma 5-upla (K, Σ, δ, e0, F), onde:
• K é um conjunto finito de estados;
• Σ é o alfabeto dos símbolos da linguagem;
 Linguagens Formais e Autômatos – 1º Semestre de 2015
• δ é a função de transição dos estados;
• e0 é o estado inicial; e
• F os estados finais.
Exemplo: O autômato M abaixo reconhece números inteiros e reais (separados por “.”).
M = (K, Σ, δ, e0, F), onde:
K = (E0 , E1 ,E2 , E3)
Σ = (d, .)
δ(E0,d) → E1
δ(E1,d) → E1
δ(E1,.) → E2
δ(E2,d) → E3
δ(E3,d) → E3
e0 = E0
F = (E1 , E3)
b) Tabela de Transições
Uma segunda maneira de representar um autômato finito é por meio de uma tabela de transições de 
estados, contendo os estados nas linhas e os símbolos do alfabeto nas colunas. O estado inicial é 
marcado com uma seta e os finais com um círculo.
Exemplo: A tabela a seguir representa o autômato do exemplo anterior:
 Linguagens Formais e Autômatos – 1º Semestre de 2015
d .
E0 E1
E1 E1 E2
E2 E3
E3 E3
Diz-se que uma cadeia é aceita por um autômato (pertence à linguagem, gerando uma 
sentença) se, após o seu processamento o autômato pára em um estado final. Se durante o 
processamento ocorre uma situação de indefinição, o autômato pára e a sentença não é aceita, como 
uma transição de e0 seguido de um ponto, no exemplo anterior.
c) Diagrama de Estados
Um autômato finito pode ser representado por meio de um Diagrama de estados (Grafo), no 
qual os nodos representam os estados e os arcos, as transições. O estado final é indicado por uma 
seta e os finais por circunferências concêntricas.
Exemplo: Para o exemplo anterior, o diagrama de estados que representa o autômato é mostrado a 
seguir:
 Linguagens Formais e Autômatos – 1º Semestre de 2015
4.1.2 – Conversão entre Formato de Reconhecedores
Muitas vezes, os diagramas de estados aparecem como primeira forma de representação para 
os autômatos, por causa de sua apresentação gráfica e facilidade de leitura pelo projetista. Para o 
computador, entretanto, formas tabulares são indiscutivelmente mais cômodas e eficientes. Assim, a 
conversão de uma notação para a outra torna-se conveniente para efeito de implementação e de 
documentação. Para converter diagramas de estados em tabelas de transições, pode-se seguir as 
seguintes regras:
§ Cria-se uma linha na tabela de transição para cada estado do diagrama;
§ Marcam-se os estados finais (de aceitação) e o estado inicial;
§ Cria-se uma coluna para cada terminal e não terminal utilizados no diagrama;
§ Cria-se uma coluna adicional para representar quaisquer outros terminais de 
linguagem que não estejam sendo explicitamente utilizados no diagrama;
§ Se necessário, cria-se uma coluna adicional para transições em vazio;
§ Para cada transição do estado i para o estado j, consumindo um átomo α, insere-se, 
na coluna correspondente a α, da linha correspondente ao estado i, a indicação de 
transição para o estado j. Note-se que as células da tabela, inicialmente vazias, vão 
sendo preenchidas com os estados-destino das transições. Note-se ainda que, se o 
autômato apresentar mais de uma transição partindo do estado i, e consumindo o 
mesmo átomo, a célula correspondente representará o conjunto dos estados-destino 
para o caso em questão; e
§ Proceder analogamente para transições com não-terminais e para transições em 
vazio, utilizando as colunas correspondentes.
A conversão oposta pode ser efetuada de maneira semelhante:
§ Cria-se, para cada linha da tabela, um estado no diagrama;
§ Marcam-se os estados iniciais e finais;
§ Para cada célula da tabela, correspondente ao estado i, e ao consumo de um terminal 
α, que indique transições para um conjunto de estados-destino{j1,...,jn}, criar , no 
 Linguagens Formais e Autômatos – 1º Semestre de 2015
diagrama de estados. Caminhos orientados do estado i para os estados j1,...,jn, com 
indicação do consumo do terminal α. Se o conjunto for vazio, nada há a fazer;
§ Tratar de modo similar as células pertencentes a colunas correspondentes a não-
terminais e à transição em vazio; e
§ Para uma eventual célula não vazia do estado i, pertencente à coluna correspondente 
a todos os demais terminais não explícitos na tabela, criar para cada um destes 
terminais (α) caminhos orientados partindo do estado i para cada um dos estados-
destino indicados na célula.
A conversão da notação de autômatos finitos, de produções para diagramas de estados, bem como a 
conversão oposta, é trivial, e baseia-se nas regras seguintes: 
§ Levantam-se inicialmente: o conjunto de estados utilizados nas produções ou nos 
diagramas, o estado inicial e os estados finais do autômato.
§ As transições com consumo de átomos são mapeadas de uma notação para outra com 
a seguinte correspondência:
(Qi, a) → Qj§ Transições em vazio são mapeadas analogamente.
(Qi, ∈) → Qj
4.2 – Reconhecedores Determinísticos e Não-Determinísticos
Os reconhecedores podem se dividir em duas categorias: os reconhecedores determinístico e 
os reconhecedores não-determinísticos.
Reconhecedores determinísticos são definidos como aqueles que possuem um único 
movimento possível para uma dada configuração, enquanto que os reconhecedores não-
determinísticos admitem um número finito, maior ou igual a um, de movimentos para cada 
configuração. 
Logo, o autômato finito pode ser determinístico (AFD) e não determinístico (AFN). No AFD 
cada movimento é determinado de uma única forma, enquanto que no AFN existem várias 
 Linguagens Formais e Autômatos – 1º Semestre de 2015
possibilidades de transição para um mesmo símbolo. Em alguns livros cita-se que um AFN pode ter 
movimentos vazios. Um movimento vazio é uma transição sem leitura de símbolo algum. 
Isso implica dizer que reconhecedores determinísticos possuem apenas uma seqüência de 
movimento para cada cadeia aceita. Este é um ponto muito importante quando se está preocupado 
com desempenho. Felizmente pode-se provar que se dois reconhecedores, um determinístico e outro 
não-determinístico, definem a mesma linguagem, então é possível mapear qualquer reconhecedor 
não-determinístico em um determinístico equivalente.
Exemplos:
AFD
AFN
4.3 – O Mapeamento de Autômatos Finitos em Gramáticas Regulares
Para completar este estudo sobre autômatos finitos, cumpre mencionar que, às vezes, dado 
um autômato finito determinístico já montado deseja-se construir uma gramática que gere a mesma 
linguagem. Esta gramática pode ser construída trivialmente aplicando-se as seguintes regras de 
mapeamento:
§ Para cada produção do autômato da forma (q1, x) → q2 construir uma produção 
gramatical da forma Q1 → xQ2 , onde Q1 e Q2 são não-terminais correspondentes 
aos estados q1 e q2 respectivamente, e x é um terminal.
§ Para cada produção (q1, x) → q2 , onde q2 é um estado final do autômato, acrescentar 
 Linguagens Formais e Autômatos – 1º Semestre de 2015
uma produção gramatical da forma Q1 → x à gramática que está sendo construída.
Exemplo: Dado o Autômato Finito, representado na tabela, obtém-se a gramática correspondente:
t i < n > ,
 A B
B E
C F
D B
E C B
F D C
P: A → tB
 B → iE 
B → i
C → nF
D → , B
 E → < C
E → , B
F → > D
F → >
F → , C
A gramática desejada será:
G = ( { A, B, C, D, E, F, > , < , , , i, t, n}, {> , < , , , i, t, n}, P, A), onde P é o conjunto das 
produções da gramática apresentado acima.
	3 - Tipos de Gramáticas Segundo a Hierarquia de Chomsky
	3.1 - Gramáticas Irrestritas
	3.2 - Gramáticas Sensíveis ao Contexto
	3.3 - Gramáticas Livres de Contexto
	3.4 - Gramáticas Regulares
	3.5 - Expressões Regulares
	4 – Linguagens Regulares
	4.1 - Reconhecedores
	4.1.1 – Formato de Reconhecedores
	4.1.2 – Conversão entre Formato de Reconhecedores
	4.2 – Reconhecedores Determinísticos e Não-Determinísticos
	4.3 – O Mapeamento de Autômatos Finitos em Gramáticas Regulares

Outros materiais