Teoria Computacao Novo

Prévia do material em texto

MSc. Roberto Cruz Acosta 
1 
 
 
 
 
 
 
 
 
 
 
 
Teoria 
 
 
 
 
 
 
 
 
da 
 
 
 
 
 
 
 
 
Computação 
 
 
 
 
 
 
 
 
 
 
 
 
Março/2018 
MSc. Roberto Cruz Acosta 
2 
 
 
 
 
Objetivo desta apostila 
 
Esta apostila foi desenvolvida com o objetivo de facilitar o entendimento da Teoria da 
Computação, principalmente no que se refere às Linguagens Formais e Autômatos. Na 
sua elaboração foram utilizados os principais livros-textos adotados em disciplinas dessa 
área. 
 
Os exemplos apresentados são bastante simples, visando fins didáticos. Portanto, esta 
apostila NÃO substitui os livros-textos, sendo apenas um material auxiliar. 
 
 
Agradecemos antecipadamente. 
 
MSc. Roberto Cruz Acosta 
3 
 
 
 
1. Introdução 
 
Teoria da Computação. A Teoria da Computação abrange o estudo de modelos de 
computadores ou máquinas e o respectivo poder computacional destes modelos. Isto 
é, que classes de problemas podem ser resolvidas em cada modelo e como 
representá-los. 
 
O modelo de computação atual (ano base: 2007) é incapaz de entender a linguagem 
humana direta: seja falada ou escrita, dado o número enorme de possibilidades de 
significados e/ou acepções de uma mesma palavra, além das variações de 
construções de frases. 
 
Linguagens Formais. Para diminuir este distanciamento entre a língua humana (por 
exemplo: o português, o inglês, etc.) e a programação de computadores foram 
criadas as linguagens de programação. Estas são linguagens formais, isto é, 
procuram eliminar toda ambigüidade possível, garantindo assim que um comando e 
palavras reservadas tenham sempre o mesmo significado independentemente de 
onde apareçam no programa. 
 
A língua portuguesa é uma linguagem natural, sendo que sua representação escrita 
possui uma gramática. Esta indica onde se deve usar preposição ou não; a 
concordância verbal e nominal, entre outras regras. 
 
Gramáticas. Da mesma forma, as linguagens de programação possuem uma 
gramática associada, que define a formação de programas válidos. Por exemplo: se 
cada comando deve ser seguido de ; (ponto-e-vírgula), se o tipo de uma variável vem 
antes ou depois de seu nome. 
 
Algoritmos. As resoluções de problemas são representadas através de algoritmos, 
sendo que esses são implementados computacionalmente em alguma linguagem de 
programação. 
 
Compiladores. Os compiladores fazem tradução dos programas escritos nas 
diversas linguagens de programação para instruções que o computador é capaz de 
executar. Assim, a Teoria da Computação está intimamente ligada ao estudo de 
linguagens: sua representação (gramática); e sua tradução para instruções da 
máquina usada (compilador). 
 
2. Gramáticas e Linguagens Formais 
 
Uma gramática define a estrutura geral de formação de uma sentença válida para 
uma linguagem. Suponha o seguinte exemplo simplificado para a Língua Portuguesa: 
 
<Frase> ::= <Sujeito> <Predicado> 
<Sujeito> ::= <Artigo> <Substantivo> 
<Predicado> ::= < Verbo> <Complemento> 
<Complemento> ::= <Artigo> <Substantivo> 
<Artigo> ::= “o” | “a” 
<Substantivo> ::= “livro” | “mente” 
<Verbo> ::= “abre” 
MSc. Roberto Cruz Acosta 
4 
 
 
 
Forma Normal de Backus. A gramática anterior está especificada numa notação 
conhecida como Forma Normal de Backus (BNF). Nessa notação, as palavras entre 
os símbolos < e > são chamadas variáveis. O símbolo ::= indica que a variável à sua 
esquerda pode ser substituída pelos valores à direita. 
 
Assim, a gramática anterior estabelece que uma frase é formada por um sujeito 
seguido de um predicado, sendo que este por sua vez é formado por um verbo 
seguido de um complemento. E portanto, a frase “o livro abre a mente” é uma frase 
válida segundo a gramática acima. 
 
Em uma linguagem de programação teríamos, por exemplo, uma regra que define um 
comando de atribuição válido: 
 
<Atribuicao> ::= <Variável> “:=” <Valor> “;” 
onde <Variável> se refere a qualquer seqüência de caracteres começando com 
alguma letra. 
 
A descrição de gramáticas seguindo essa forma, embora de simples entendimento, 
não é muito prática quando se deseja estudar mais genericamente as propriedades 
das linguagens. Assim, na teoria da computação geralmente é dado um tratamento 
matemático às linguagens e adotam-se convenções de notação e simplificações, 
procurando facilitar sua representação e o estudo de suas propriedades. 
 
Exemplo de convenções: ao invés de se escrever <Variável>, em geral utiliza-se 
apenas uma letra maiúscula (V) para representar tais tipos de construção. 
 
Além disso, na Teoria da Computação, em geral procura-se estudar classes de 
linguagens ao invés de uma linguagem específica. 
 
A seguir, algumas definições essenciais para o estudo de Linguagens Formais: 
 
2.1 Alfabeto (Σ): é um conjunto finito de símbolos. 
Na língua portuguesa seria formado pelas 27 letras do alfabeto mais os dígitos de 0 a 
9. 
Outros exemplos: o alfabeto grego, o alfabeto russo. 
 
Usamos a letra grega sigma maiúscula (Σ) para representar o alfabeto de uma 
linguagem. 
Ex.: Σ = {0,1} representa o alfabeto composto pelos símbolos 0 e 1. 
 
2.2 Palavra ou cadeia: é uma seqüência finita de símbolos do alfabeto concatenados 
Exemplos de palavras utilizando o alfabeto Σ = {0,1}: 0, 1, 010, 111, 011, etc. 
 
O comprimento de uma cadeia w, denotado por |w| é o número de símbolos que 
compõem w. Assim a palavra 011 tem comprimento 3 (três). 
 
Usamos a letra grega epsilon minúscula (ε) para representar a palavra vazia, isto é, ε 
tem comprimento 0 (zero). 
MSc. Roberto Cruz Acosta 
5 
 
 
O símbolo Σ* indica o conjunto de todas as palavras possíveis de serem formadas a 
partir do alfabeto Σ , de qualquer comprimento incluindo a palavra vazia (ε). 
 
A notação an indica a repetição do símbolo a n vezes. Assim a3 representa aaa, a2 
representa aa e a0 representa ε (palavra vazia). 
 
2.3 Linguagem Formal: é um conjunto de palavras sobre um alfabeto. 
Exemplos de linguagens formais sobre o alfabeto Σ = {0,1}: 
a) L = { 01, 1010, 1110} representa a linguagem formada pelas cadeias 01, 1010 e 
1110 somente. 
b) L = { w | w tem número ímpar de zeros em Σ*} representada todas cadeias 
possíveis com número ímpar de zeros usando somente os símbolos 0 e 1. 
 
 
 
3. Representação de Linguagens Formais 
 
Uma linguagem formal pode ser representada de 3 maneiras: 
• Enumeração das cadeias que fazem parte dela. 
• Gramática, isto é, um conjunto de regras que especifica a formação das 
cadeias. 
• Dispositivo reconhecedor (máquina), que possui embutido um conjunto de 
regras de aceitação de cadeias. 
 
A primeira só pode ser utilizada para linguagens finitas. As duas últimas são capazes 
de representar linguagens com número infinito de cadeias. 
 
Gramática. A definição formal de uma gramática é uma quádrupla ordenada 
G = (V,T, P,S), onde: 
• V é o conjunto de símbolos não-terminais, também chamados de variáveis 
• T é o conjunto de símbolos terminais, tal que V ∩ T = Ø 
• P é o conjunto de regras de produção 
• S é o elemento de V denominado símbolo inicial 
 
As regras de produção são escritas na forma α→β , onde α e β são compostos de 
não-terminais e terminais; além disso, α possui pelo menos um não-terminal. 
 
Convenções. As seguintes convenções de notação são adotadas: 
• Cada não-terminal é representado por apenas uma letra maiúscula do alfabeto 
português {A, B, C, D, ...} 
• Cada terminal é representadopor apenas uma letra minúscula ou dígito 
{0,1,2,3,4,5,6,7,8,9, a,b,c,d,...} 
• Utiliza-se a própria letra maiúscula S para ser o símbolo inicial da gramática. 
 
Exemplo 1: Seja G a gramática: 
S → AB 
A → aA | a 
B → b 
 
Neste exemplo a gramática possui 4 regras: S → AB, A → aA, A → a e B → b 
. 
MSc. Roberto Cruz Acosta 
6 
 
 
O símbolo | pode ser usado quando há mais de uma regra para um mesmo não 
terminal, como o não-terminal A do exemplo. 
 
O conjunto de não-terminais para a gramática G é V= {S,A,B}. O conjunto de 
terminais T = {a,b} . O conjunto de regras P = { S → AB, A → aA, A → a, B → b }. 
A seta (→) indica que o não-terminal à sua esquerda pode ser substituído pelo 
símbolo ou símbolos que estão à sua direita. Assim: 
• o não-terminal S pode ser substituído por AB 
• o não-terminal A pode ser substituído por aA ou por a 
• o não-terminal B pode ser substituído por b. 
 
As palavras ou cadeias válidas na linguagem são formadas a partir do símbolo inicial, 
substituindo-o por alguma de suas regras e os não-terminais desta sucessivamente, 
até que se obtenham apenas terminais. Assim, utilizando a gramática definida 
anteriormente pode-se obter a palavra aaab efetuando-se as seguintes substituições: 
 
(1) S ⇒ AB (2)
 ⇒ aAB 
(3) ⇒ aaAB 
(4) ⇒ aaaB 
(5) ⇒ aaab 
 
Na linha (1) foi usada a única regra disponível para o símbolo S. Na linha (2) foi usada 
a regra A → aA. Na linha (3) foi usada novamente a regra A → aA. Na linha (4) foi 
usada a regra A → a. Na linha (5) foi usada a regra B → b. 
 
Observe que a notação usada no processo de substituição, indica pela seta ⇒ , é 
diferente da notação usada na própria gramática, indicada pela seta →. Isto permite 
diferenciar quando se está gerando uma palavra ou descrevendo uma regra da 
gramática. 
 
Derivação. O processo de substituir um não-terminal por alguma de suas regras é 
chamado de derivação. 
 
Árvore de derivação. A geração de uma palavra pelas sucessivas derivações pode 
ser representada através de uma árvore, chamada árvore de derivação, onde a raiz 
é o símbolo inicial S. A Figura 1 apresenta a árvore de derivação para a palavra aaab 
do exemplo anterior. 
 
S 
 
A B 
 
a 
A 
b 
a A 
 
 
a 
Figura 1 
MSc. Roberto Cruz Acosta 
7 
 
 
Efetuando-se todas as possíveis derivações a partir do símbolo inicial S, obtêm-se 
todas as palavras que compõem a linguagem formal descrita pela gramática, 
podendo ser infinito o número de palavras. 
 
No exemplo da gramática anterior é possível gerar o seguinte conjunto infinito de 
palavras: L = {ab, aab, aaab, aaaab, aaaaab, ...}. Observando mais atentamente as 
palavras geradas é fácil notar que todas seguem um padrão: são formadas por uma 
seqüência de um ou mais a’s e terminadas exatamente com um b. Assim pode-se 
dizer a gramática representa ou gera a linguagem L = { w | w é formada por uma 
seqüência de um ou mais a’s seguido de exatamente um b sobre Σ*}, onde Σ = {a,b}. 
 
Linguagens de Programação. A gramática de uma linguagem de programação 
representa todos os programas possíveis de serem escritos nela, geralmente um 
número potencialmente infinito de programas. Assim, o primeiro trabalho do(s) 
criador(es) de uma linguagem de programação é definir sua gramática. 
 
Notação. Usa-se L(G) para denotar a linguagem gerada pela gramática G. 
 
Gramáticas equivalentes. Uma mesma linguagem pode ser gerada por diferentes 
gramáticas. Por exemplo, a gramática: 
S → Ab 
A → aA | a 
gera a mesma linguagem descrita pela gramática vista anteriormente. Assim, quando 
duas gramáticas geram a mesma linguagem, elas são ditas gramáticas equivalentes. 
Formalmente: G1 é equivalente a G2 se e somente se L(G1) = L(G2). 
 
No estudo das linguagens formais, as gramáticas são classificadas de acordo com as 
restrições que se impõem sobre suas regras de produção. Assim, as linguagens 
formais podem ser classificadas em: 
• Linguagens Regulares (Tipo 3) - LR 
• Linguagens Livres de Contexto (Tipo 2) - LLC 
• Linguagens Sensíveis ao Contexto (Tipo 1) - LSC 
• Linguagens Recursivamente Enumeráveis (Tipo 0) - LRE 
 
 
A Figura 2 mostra a relação entre os tipos de linguagens. 
 
 
LR 
 
 
LLC 
 
 
LSC 
 
LRE 
 
 
Figura 2 
As linguagens regulares (LR) são aquelas onde se impõem mais restrições às regras 
de produção. 
MSc. Roberto Cruz Acosta 
8 
 
 
 
Hierarquia de Chomsky. As linguagens livres de contexto (LLC) são menos 
restritivas que as linguagens regulares (LR). As linguagens sensíveis ao contexto 
(LSC) são menos restritivas que linguagens livres de contexto (LLC) e assim por 
diante. A hierarquia assim gerada é chamada de Hierarquia de Chomsky. 
 
Devido ao fato que um tipo de linguagem com mais restrições é um caso particular de 
um tipo de linguagem com menos restrições, então toda LR é uma LLC. Toda LLC é 
uma LSC, e toda LSC é uma LRE. 
 
Estudaremos inicialmente apenas as linguagens regulares (LR). 
 
Gramática Regular (GR). Uma gramática G é regular se todas suas produções são 
tais que podem ser colocada em alguma das seguintes formas: 
• A→ a 
• A→ aB 
• A→ ε 
 
Isto é, do lado esquerdo da regra sempre há somente um não-terminal. Do lado 
direito há um terminal sozinho (acompanhado no máximo de um não-terminal), ou há 
apenas a palavra vazia (ε). 
 
Ás vezes, inicialmente a gramática não possui todas suas regras em alguma das 
formas segundo a definição de gramática regular. No entanto, fazendo-se pequenas 
alterações é possível obter uma gramática equivalente onde todas as regras estejam 
de acordo com a definição de gramática regular. Exemplo: seja G1 a gramática a 
seguir: 
 
S → AB 
A → aA | a 
B → b 
 
G1 é regular. Para ver isto, basta observar que ela é equivalente a G2, definida por: 
 
S → aA 
A → aA | b 
 
Linguagem Regular (LR). Uma linguagem é regular se ela pode ser descrita usando 
uma gramática regular (GR). 
 
4. Modelos de Máquinas 
 
Dispositivo Reconhecedor. Uma outra maneira de definir uma linguagem é através 
da utilização de um dispositivo reconhecedor, que permite submeter uma palavra ou 
cadeia a um teste de aceitação capaz de determinar se tal palavra pertence ou não à 
linguagem em questão. 
 
O dispositivo reconhecedor é na verdade um modelo matemático que descreve o 
funcionamento de uma máquina, onde as cadeias são submetidas para aceitação ou 
rejeição. 
MSc. Roberto Cruz Acosta 
9 
 
 
Cada tipo de linguagem da Hierarquia de Chomsky possui um reconhecer distinto. 
 
Linguagem Reconhecedor 
Linguagens Regulares (LR) Autômatos Finitos 
Linguagens Livres de Contexto (LLC) Autômatos com Pilha 
Linguagens Sensíveis ao Contexto 
(LSC) 
Máquina de Turing com memória 
limitada 
Linguagens Recursivamente 
Enumeráveis (LRE) 
Máquina de Turing 
 
Inicialmente estudaremos os autômatos finitos, capazes de reconhecer linguagens 
regulares (LR). 
 
 
 
5. Autômato Finito Determinístico (AFD) 
 
Definição. Um Autômato Finito Determinístico (AFD) é um modelo de máquina 
definido formalmente por uma quíntupla M = (Σ , Q, δ, q0, F), onde: 
• Σ : alfabeto de símbolos de entrada 
• Q: conjunto finito de estados possíveis para M 
• δ: função transição ou função programa definida em Q x Σ → Q 
• q0: estado inicial de M, sendo q0 ∈Q 
• F: conjunto de estados finais, tal que F ⊆ Q 
 
 
 
 
a a b a b … fita de entrada 
 
cabeça de leitura 
 
q0 
q1 
qn 
… q2 
 
 
 
 
 
controle finito 
 
 
 
 
 
 
Figura 3 
 
Um AFDpode ser representado esquematicamente conforme a Figura 3: os símbolos 
que compõem a palavra a ser testada encontram-se escritos numa fita de entrada, 
dividida em células, onde cada símbolo ocupa exatamente uma célula. Há um controle 
finito composto pelos estados possíveis para o autômato, sendo que existe um 
marcador que indica o estado atual. Além disso, há uma cabeça de leitura que lê um 
símbolo por vez da fita. 
 
Finito. O autômato é dito finito porque o conjunto de estados possíveis (Q) é finito. 
 
Determinístico. O autômato é determinístico quando dado o estado atual de M, ao ler 
um determinado símbolo na finita de entrada existe apenas um próximo estado 
possível. 
MSc. Roberto Cruz Acosta 
10 
 
 
Estado Inicial. O estado inicial q0 indica que ao “ligarmos” o AFD, o marcador 
automaticamente se posiciona no estado q0, antes de ler qualquer símbolo da fita de 
entrada. Só pode existir um único estado inicial. 
 
Aceitação. Uma palavra é reconhecida (ou aceita) quando o AFD após ler todos os 
símbolos contidos na fita de entrada, o marcador se encontrar em um estado final. Ao 
contrário do estado inicial, podem existir vários estados finais. 
 
Rejeição. Uma palavra é rejeitada quando após ler todos os símbolos da fita de 
entrada, o marcador não se encontrar em um estado final ou quando não existe uma 
transição definida para um símbolo a ser lido, estando o autômato num determinado 
estado. 
 
Máquina de Estados Finitos. Alguns autores denominam os AFDs de máquinas de 
estados finitos. 
 
Vejamos um exemplo de AFD: 
 
Seja M = (Σ,Q, δ,q0,F) tal que Σ = {a,b}, Q = {q0, q1, q2}, F = {q2} e a função transição 
(ou função programa) δ definida segunda a tabela a seguir: 
 
 
δ a b 
q0 q1 --- 
q1 q1 q2 
q2 --- --- 
 
Interpretando a tabela: estando no estado q0 e lendo o símbolo a na fita de entrada, M 
muda para o estado q1. Também estando no estado q0 e lendo o símbolo b na fita de 
entra, M rejeita a palavra, pois não há transição definida esta situação. Já estando no 
estado q1, e lendo o símbolo a, M permanece no estado q1. Quando M está no estado 
q1 e lê um símbolo b, ele muda para o estado q2. E uma vez no estado q2, qualquer 
símbolo que seja lido, a palavra será rejeitada, pois não há transições definidas a partir 
de q2. 
 
Grafo Orientado. Comumente representa-se a função programa (δ) utilizando-se um 
grafo orientado. A Figura 4 apresenta o grafo correspondente à função programa do AFD 
do exemplo anterior. 
 
a 
a b 
 
 
q0 q1 q2 
 
Figura 4 
 
Os nós do grafo representam os estados possíveis do AFD enquanto as arestas 
orientadas representam as transições. A origem de uma seta indica o estado atual. O 
símbolo a ser lido é colocado sobre a seta. 
MSc. Roberto Cruz Acosta 
11 
 
 
O destino da seta indica o próximo estado após a leitura do símbolo. O estado inicial é 
indicado através de uma seta sem origem e com destino no estado inicial. Os estados 
finais são indicados através de dois círculos concêntricos. 
 
Observando o grafo do AFD temos os estados q0, q1 e q2, sendo q0 o estado inicial e q2 
o estado final. O estado q1 pode ser traduzido como “estado onde se lê um ou mais a’s. 
O estado q2 pode ser expresso por: “estado que indica a leitura de exatamente um b”. 
 
Este AFD reconhece a linguagem L = { w | w é formada por uma seqüência de um ou 
mais a’s seguido de exatamente um b sobre Σ*}, onde Σ = {a,b}. Portanto, é 
equivalente à gramática vista anteriormente: 
 
S → AB 
A → aA | a 
B → b 
 
Teorema: Toda linguagem regular (LR) possui um AFD equivalente. 
 
Outro exemplo: seja L = { ab
n
c
m 
| n ≥ 0 e m ≥ 0}. O AFD a seguir reconhece L. 
 
 
b c 
a c 
 
q0 q1 q2 
 
 
Figura 5 
 
M = (Σ, Q, δ, q0, F) onde Σ = {a, b, c}, Q = {q0, q1, q2}, δ está representada pelo grafo da 
Figura 5, q0 é o estado inicial e F = {q1, q2}. Exemplos de palavras ou cadeias 
reconhecidas pelo AFD : a, ab, ab, abb, abbb, abc, abbc, abcc, ac, acc, accc, etc. 
Exemplos de cadeias não reconhecidas: b, c, ba, acb, aa, etc. 
 
 
 
6. Transformação de AFD em Gramática Regular (GR) 
 
É possível escrever uma gramática regular para todo AFD. Para tal basta seguir o 
algoritmo a seguir: 
• a cada estado é associado um não-terminal da gramática, sendo o estado 
inicial q0 associado ao símbolo inicial (S) 
• para cada transição de estado representada no grafo cria-se uma regra de 
produção na gramática, tal que o estado de origem torna-se o não-terminal à 
esquerda da regra e o estado destino torna-se um não-terminal do lado direita 
da regra após o terminal lido na transição. 
• cria-se uma regra para cada não-terminal associado a um estado final onde o 
lado direito da regra é formado apenas pela palavra vazia (ε). 
MSc. Roberto Cruz Acosta 
12 
 
 
Como exemplo considere o AFD da Figura 5. Fazendo-se q0 = S, q1 = A e q2 = B, a 
gramática equivalente ao AFD é: 
 
 
 
S → aA 
A → bA | cB | ε 
B → cB | ε 
 
 
 
7. Transformação de Gramática Regular (GR) em AFD 
 
O algoritmo a seguir mostra como encontrar um AFD equivalente a uma dada gramática 
regular. Todas as regras da gramática devem ser do tipo A → aB (não-terminal levando 
a um terminal seguido de um único não-terminal) ou A → a (não-terminhal levando a 
um terminal sozinho) ou A → ε (não-terminal levando à palavra vazia). 
• Para cada não-terminal crie um estado para o AFD, sendo que o símbolo inicial 
seja o estado inicial ( S = q0 ). 
• Para cada regra do tipo A → aB crie uma transição que parta do estado A com 
destino ao estado B através da leitura do terminal a. 
• Para cada regra do tipo A → a crie uma transição que parta do estado A com 
destino a um estado Ax, através da leitura do terminal a. Além disso, marque o 
estado como final 
• Para cada regra do tipo A → ε, faça do estado associado ao não-terminal A 
um estado final. 
 
A Figura 6 mostra o AFD equivalente à gramática regular a seguir: 
 
S → aA | bB 
A → aA | bB | c | ε 
B → bB | ε 
 
 
b 
a 
a b 
 
 
A B 
 
S c 
 
 
A1 
 
 
b 
Figura 6 
MSc. Roberto Cruz Acosta 
13 
 
 
8. Expressões Regulares (ER) 
 
As linguagens regulares podem ser representadas usando uma notação denominada 
expressão regular. Uma expressão regular utiliza apenas símbolos terminais e alguns 
caracteres especiais (metacaracteres), sendo que estes têm a função de especificar a 
quantidade de vezes que um terminal ou grupo de símbolos terminais se repetem dentro 
da formação de uma palavra pertencente à linguagem. 
 
Definição. A definição formal de uma expressão regular pode ser feita recursivamente da 
seguinte maneira: 
• Se x é um terminal, x é expressão regular. 
• Se r e s são expressões regulares, então r+s é expressão regular. O sinal + 
indica que tanto r ou s formam palavras válidas 
• Se r e s são expressões regulares, então rs é expressão regular, onde as 
palavras são formadas pela concatenação de r e s. 
• Se r é expressão regular, r* denota a expressão regular onde r é repetida zero 
ou mais vezes 
• Se r é expressão regular, r+ denota a expressão regular onde r é repetida uma 
ou mais vezes. Portanto r
+ 
= rr
*
 
• Utilizam-se parêntesis para agrupar símbolos que se repetem conjuntamente. 
 
Exemplos: 
• 001(0+1) denota L = {0010, 0011} 
• 01(10+11) denota L = { 0110, 0111} 
• (0 + 01)1 denota L = { 01, 011} 
• ab*a denota L = {aa, aba, abba, abbba, ...}, isto é, L = { w | w inicia com um 
a seguido de zero ou mais b’s e termina com um a} 
• a(bc)*a denota L = {aa,abca, abcbca, abcbcbca, ...}, isto é, L = { w | w 
inicia-se com um a seguido de zero ou mais seqüências de bc e termina 
com a} 
• ab+a denota L = {aba, abba, abbba, ...}, isto é, L = { w | w inicia-se com um 
a seguido de um ou mais b’s e termina com a} 
• (ab + bc)a denota L = {aba, bca} 
• (a+b)* denota L = {a,b}*, isto é todas as palavras possíveis de serem 
formadas a partir do símbolos a e b, inclusive a palavra vazia. 
• (a+b)*c(a+b)* denota L = { w | w possui exatamente um c sobre Σ = {a,b,c}* } 
 
Unix. O comando grep do sistema operacional Unix permite o uso de expressões 
regulares para busca de padrões. 
 
Exemplos: 
• grep “Mar*” arq: listará todas as linhas do arquivo arq que contêm 
palavras contendo a string Mar. 
• grep Maria arq* : listará todas as linhas de arquivos cujo nome 
comece com arq e que contenha a string Maria. 
• grep –i maria arq : listará todas as linhas do arquivo arq que 
contenham a string maria (ignorando maiúsculas e minúsculas). 
• grep –v maria arq : listará todas as linhas do arquivo arq que não 
contenham a string maria. 
MSc. Roberto Cruz Acosta 
14 
 
 
• grep “[a-z]” arq: listará todas as linhas do arquivo arq que comecem 
com as letras minúsculas de a a z. 
 
9. Autômatos Finitos Não-determinísticos (AFND) 
 
Definição. Um autômato finito não-determinístico (AFND) é similar a um AFD, porém 
existe pelo menos um estado tal que ao ler um mesmo símbolo há mais de uma 
possibilidade de estado destino. 
 
c 
a b 
 
q0 q1 q2 
 
a 
Figura 7 
 
No autômato da Figura 7, existem duas transições de estado possíveis ao ler o símbolo 
a estando o autômato no estado q0. 
 
Aceitação. Uma cadeia é aceita por um AFND se testando-se todas as transições 
possíveis à medida que se lê a cadeia, o AFND pára em um estado final após ler toda a 
cadeia para algum caminho das transições. Assim, o não-determinismo do próximo 
estado pode ser interpretado como um teste de todas as possibilidades. 
 
Exemplos de cadeias aceitas pelo AFND da figura 7: a, ac, ab, abcc, ... 
 
Rejeição. Uma cadeia é rejeita por um AFND se nenhum caminho de transições leva o 
autômato a um estado final após ler toda a cadeia. 
 
Exemplos de cadeias rejeitadas pelo AFND da figura 7: b, bc, abb, aca, ... 
 
 
10. Autômatos Finitos com Transições ε (AFε) 
 
Definição. Um autômato finito com transições ε (AFε) é um AFND onde existem 
transições feitas a partir da palavra vazia. 
 
Uma transição a partir da palavra vazia indica que o autômato pode alterar seu estado 
sem ler nenhum símbolo da fita. 
 
AFND. A existência de apenas uma transição usando a palavra vazia é suficiente para 
que o autômato seja considerado não-derterminístico (AFND), pois existe uma situação 
o autômato pode efetuar uma transição sem ler qualquer símbolo da fita. 
 
Aceitação e Rejeição. A aceitação e rejeição de cadeias são feitas do mesmo modo 
que em AFND. 
MSc. Roberto Cruz Acosta 
15 
 
 
c 
ε b 
 
q0 q1 q2 
 
a 
 
Figura 8 
 
No AFε da Figura 8, o autômato pode fazer a transição para o estado q1 a partir do 
estado q0 sem ler qualquer símbolo na fita. Assim, as cadeias: b, bc, bcc são aceitas 
pelo autômato enquanto que bb, aac, acb são rejeitadas. 
 
Teorema. Para todo AFND, incluindo os AFε, é possível construir um AFD equivalente. 
 
Equivalência. Na prática, o teorema anterior estabelece que a facilidade de não- 
determinismo dos AFNDs não representa um aumento de “poder” computacional em 
relação aos AFDs. Ou seja, a classe de linguagens reconhecida por AFNDs e AFDs é a 
mesma. 
 
11. Transformação de Expressões Regulares em AFε 
 
Existe um algoritmo simples para conversão de expressões regulares em AFε. Segue 
sua descrição: 
 
• Se uma expressão regular r é constituída por um único símbolo x, então r pode 
ser representada por um autômato de apenas 2 (dois) estados, tal que existe 
uma transição do primeiro para o segundo estado lendo o símbolo x. 
• Se uma expressão regular r é da forma r = r1 + r2, isto é, as palavras válidas 
são palavras da linguagem descrita por r1 ou da linguagem descrita por r2, 
então r pode ser representada pela união dos autômatos M1 e M2, que 
reconhecem r1 e r2 respectivamente, de maneira que M1 e M2 formem 
caminhos exclusivos entre si utilizando transições ε. 
• Se uma expressão regular r é da forma r = r1r2, isto é, as palavras válidas são 
obtidas da concatenação das palavras da linguagem descrita por r1 com 
palavras da linguagem descrita por r2, então r pode ser representada pelo 
seqüenciamento dos autômatos M1 e M2, que reconhecem r1 e r2 
respectivamente, de maneira que M2 segue M1 utilizando uma transição ε. 
• Apenas o estado que não possui transições com origem nele é um estado 
final. 
 
Inicialmente procura-se desenhar os autômatos dos símbolos isoladamente, que são de 
fácil representação. Os autômatos obtidos são combinados segundo as regras 
anteriores até se obter o autômato que representa a expressão regular completa. 
MSc. Roberto Cruz Acosta 
16 
 
 
1 
ε ε 
x 
 
r = x 
 
 
 
 
ε M 
q0r1 qfr1 
ε 
 
 
ε 
q 
M ε 
r = r1 + r2 
0r qfr2 
 
 
 
 
 
M 
q0r1 
ε 
qfr1 
M 
q0r qfr2 
 
r = r1r2 
 
 
 
ε 
 
 
M 
q0r1 qfr1 
ε 
 
r = r1
*
 
 
 
Figura 9 
 
A Figura 9 mostra esquematicamente como pode ser feita a construção de AFε a partir 
de uma expressão regular. É importante observar que os estados que seriam finais 
em M1 e M2 para as expressões regulares r1 e r2, não o são quando se faz o autômato 
que representa r1+r2. E o mesmo ocorre com M1 em r1r2 e em r 
*
. 
 
Exemplo: seja a expressão regular (a + ab)(bc)
*
. 
Observe que ela é a concatenação das subexpressões (a +ab) e (bc)
*
. Por sua vez, (a 
+ ab) indica que apenas as palavras a e ab são válidas dentro da subepressão. Já 
(bc)
* 
é a concatenação dos símbolos b e c, repetidos em grupo, zero ou mais vezes. 
 
Assim, primeiro montamos o autômato para a primeira subexpressão (a + ab) que 
será: 
ε a ε 
 
 
 
 
a ε b 
ε ε 
Figura 10 
MSc. Roberto Cruz Acosta 
17 
 
 
Para montar o autômato para a segunda subexpressão (bc)
*
, primeiro montamos o 
autômato para bc somente, e sobre o seu resultado aplicamos a regra que permite 
repeti-lo zero ou mais vezes, obtendo assim: 
ε 
 
ε b ε c ε 
 
 
ε 
Figura 11 
 
Agora, uma vez obtidos os autômatos para (a +ab) e (bc)
* 
basta colocá-los em 
seqüência usando uma transição ε para que representem a concatenação das duas 
subexpressões, e definir o estado que não possui transições a partir dele como 
estado final, representando assim o autômato para (a + ab)(bc)
*
, conforme a Figura 
12. 
a ε 
 
 
 
a ε b 
ε 
ε 
ε 
 
ε b ε c ε 
ε 
 
Figura 12 
 
 
 
12. Transformação de AFDs em expressões regulares 
 
Conforme visto anteriormente, todo AFD possui um expressão regular equivalente. 
Segue um algoritmo para converter um AFD em expressão regular. 
• 1º passo: dado autômato M, constrói-se M’ equivalente a M, tal que o estado 
inicial de M’ liga-se ao estado inicial de M por transição ε, e todos os estados 
finais de M ligam-se ao único estado final de M’ por transição ε. Além disso, 
os estados finais de M não são finais em M’, conforme o esquema da Figura 
13. 
MSc. Roberto Cruz Acosta 
18 
 
 
 
M’: 
 
 
 
 
 
 
ε 
q0’ q0 
 
 
M ε 
qf1 
 
. . 
. . 
. . 
ε 
qfnqf’ 
 
Figura 13 
 
• 2º passo: elimina-se gradualmente os estados intermediários entre o estado 
inicial e final de M’ construindo expressões regulares equivalentes às 
transições do estado eliminado. 
 
Exemplo: Seja M o autômato da Figura 14. Inicialmente constrói-se o autômato M’, 
mostrado na Figura 15. 
 
 
c 
 
M 
 
a a q2 
c 
 
b 
q0 q1 
b 
 
q3 
 
Figura 14 
 
 
 
 
 
M’ 
 
 
 
ε 
q0’ 
 
 
 
 
a a 
 
c 
 
b 
q0 q1 
b 
c 
 
 
q2 ε 
 
 
qf 
ε 
q3 
 
 
Figura 15 
MSc. Roberto Cruz Acosta 
19 
 
 
Observe que o autômato da Figura 15 é equivalente ao autômato da Figura 14, pois 
apenas foram acrescentados dois estados (um novo estado inicial e um final) ligados 
aos respectivos estados inicial e finais usando transições ε. 
 
Agora procedemos à eliminação dos estados intermediários entre q0’ e qf. Assim, 
eliminado o estado q0 obtém-se o autômato da Figura 16. 
 
 
 
c 
 
 
 
 
 
 
 
 
q0’ 
 
 
 
 
a
*
b 
a q2 ε 
c 
 
 
q1 
b ε 
q3 
 
 
 
 
 
qf 
 
 
 
 
 
Figura 16 
 
A expressão regular colocada na transição de q0’ para q1 representa que saindo de q0’ 
até chegar em q1 foram lidos zero ou mais a’s e necessariamente um b. Isto 
corresponde exatamente ao estado eliminado (q0). 
 
Em seguida, eliminando-se o estado q1, obtém-se o autômato da Figura 17. 
 
 
c 
 
 
a
*
ba
*
c 
 
q2 ε 
 
 
q0’ 
 
 
 
 
a
*
ba
*
b 
qf 
ε 
q3 
 
Figura 17 
 
Observe que o estado q1 possui transição para dois estados distintos (q2 e q3). 
Portanto ao efetuar sua eliminação é necessário representar como que saindo de q0’ 
se chega a q2 (representado por a
*
ba
*
c), e como se chega a q3 (representado por 
a
*
ba
*
b). 
 
As Figuras 18 e 19 representam a eliminação dos estados q2 e q3, respectivamente. 
MSc. Roberto Cruz Acosta 
20 
 
 
 
 
a
*
ba
*
cc
*
 
 
 
q0’ qf 
ε 
a
*
ba
*
b 
q3 
 
Figura 18 
 
 
 
 
 
 
 
q0’ 
a
*
ba
*
cc
* 
+ a
*
ba
*
b 
qf 
 
Figura 19 
 
A expressão regular a
*
ba
*
cc
* 
+ a
*
ba
*
b é equivalente ao autômato original (M). Além 
disso, sabendo que a subexpressão cc
* 
é equivalente a c
+ 
e que a
*
ba
* 
é uma 
subexpressão comum funcionando como um prefixo para cc
* 
e b, pode-se reescrever 
a expressão da seguinte forma: a
*
ba
*
(c
+ 
+ b). 
 
Ordem de Eliminação e Equivalência. É importante registrar que a ordem de 
eliminação dos estados pode resultar em expressões regulares diferentes, porém 
equivalentes. 
 
13. Minimização de autômatos 
 
 
Definição. Um AFD M para a linguagem regular L é mínimo se qualquer outro AFD M’ 
para L, tem-se |Q| ≤ |Q’|. 
 
Portanto, um autômato é mínimo se ele possui o menor número de estados possível 
reconhecendo a linguagem em questão. 
 
Algoritmo. Dado um autômato qualquer, ele pode ser minimizado através do seguinte 
algoritmo de minimização: 
• 1º passo: transformar o AFN ou AFε em AFD 
• 2º passo: eliminar estados inúteis (aqueles a partir dos quais não é possível 
atingir um estado final) 
• 3º passo: eliminar estados inacessíveis e suas transições (aqueles que não 
podem ser atingidos a partir do estado inicial) 
• 4º passo: particionar inicialmente os estados em 2 subconjuntos: estados 
finais (F) e estados não-finais (Q – F) 
• 5º passo: calcular classes de equivalência (blocos) recursivamente a partir 
dos subconjuntos iniciais tal que: ∀p ∈ E
i 
são classes de equivalência. 
e ∀a ∈ Σ , δ ( p, a) ∈ E 
j 
onde Ei e E j 
MSc. Roberto Cruz Acosta 
21 
 
 
Exemplo: seja o autômato da Figura 20. Esse autômato já é determinístico. Portanto 
inicia-se eliminando estados inúteis. O estado q5 é um estado inútil porque não é estado 
final e não possui transições a partir dele, logo pode ser eliminado juntamente com suas 
transições, resultando no AFD apresentado na Figura 21. 
 
 
 
a 
 
 
q0 q1 
a 
b b 
 
 
q2 q3 
 
b 
a b 
 
q4 
b 
q
 
5 
 
 
a 
a 
 
Figura 20 
 
 
 
 
 
a 
 
 
q0 q1 
a 
b b 
 
 
q2 q3 
 
 
a 
a 
 
q4 
 
 
 
a 
Figura 21 
 
O AFD obtido não possui estados inacessíveis. Então passa-se à construção das 
classes de equivalência, iniciando com os conjunto Q – F = {q0,q1} e F = {q2,q3,q4}. É 
possível observar que δ (q0 , a) = q1 e δ (q1 , a) = q0 . Isto é, lendo o símbolo a a partir dos 
MSc. Roberto Cruz Acosta 
22 
 
 
estados que formam o conjunto Q – F, o AFD permanece em um estado do próprio 
conjunto Q – F. Já a leitura do símbolo b a partir dos estados do conjunto Q – F leva a 
estados do conjunto F. Além disso, a leitura do símbolo a a partir de estados do 
conjunto F, o AFD permanece no conjunto F. Assim, podemos agrupar os estados q0 e 
q1 em único estado (q01) e também os estados q2, q3 e q4 em um único estado (q234), 
gerando o AFD apresentado na Figura 22. 
 
 
 
a a 
 
 
b 
q01 
 
 
q234 
 
 
 
Figura 22 
 
 
 
14. Propriedades das Linguagens Regulares (LR) 
 
Algumas observações sobre linguagens regulares (LR), autômatos finitos 
determinísticos (AFD), gramáticas regulares (GR) e expressões regulares (ER): 
• Toda LR possui GR equivalente 
• Toda LR possui AFD que a reconhece. 
• Toda ER possui AFD equivalente 
• Toda GR possui AFD equivalente 
 
Além das observações anteriores, as linguagens regulares possuem as seguintes 
propriedades: 
• Concatenação: a concatenação de LRs resulta em LR 
• União: a união de LRs resulta em LR 
• Fecho: o fecho (repetição de zero ou mais vezes) de LR resulta em LR 
• Intersecção: a intersecção entre LRs resulta em LR 
• Complemento: o complemento (Σ* - L) de uma LR resulta em LR. 
 
Fechamento. Pelas propriedades anteriores, diz-se que a classe das linguagens 
regulares (LR) é fechada quanto às operações de concatenação, união, fecho, 
intersecção e complemento. Pois, o resultado dessas operações recai dentro da própria 
classe de linguagens regulares (LR). 
 
As operações de concatenação, união e fecho podem ser melhor visualizadas quando 
as linguagens regulares são representadas através de expressões regulares. Assim, 
sejam r e s expressões regulares para as linguagens L1 e L2. 
• rs representa a concatenação de L1 e L2. 
• sr representa a concatenação de L2 e L1. 
• r+s representa a união de L1 e L2. 
• r* representa o fecho de L1 
MSc. Roberto Cruz Acosta 
23 
 
 
15. Limitações de AFDs: exemplos de linguagens não regulares 
 
Conforme visto anteriormente, toda LR possui um AFD que a reconheça. Portanto, uma 
forma de saber se uma linguagem é regular, é construindo um AFD que a reconheça. 
 
Problema. Inversamente, se não for possível a construção do AFD, então a linguagem 
não é regular. Porém, como provar a impossibilidade de construir um AFD para uma 
dada linguagem? 
 
A seguir apresentamos o Lema do Bombeamento para LRs, usado para responder à 
pergunta anterior. 
 
Lema do Bombeamento para LRs. 
• Se L é uma linguagem regular, logo existe AFD para L com n estados, sendo 
n finito. Se uma palavra w ∈ L têm comprimento maior ou igual a n, isto é, 
|w| ≥ n, então o AFD assume algum estado mais de uma vez e portanto 
existe um ciclo no autômato. 
• w pode ser dividida em w = uvz tal que |uv| ≤ n e |v| ≥ 1, onde v é a parte 
de w reconhecida pelo ciclo. Portanto uv
iz ∈ L para i ≥ 0. 
 
Exemplo de linguagem não regular: L = {a
n
b
n 
| n ≥ 0}. 
Demonstração por absurdo: suponha que L seja regular, então pelo Lema do 
Bombeamento para LRs, w = a
n
b
n 
pode ser reescrita como w = uvz onde |uv| ≤ n e |v| 
≥ 1. Além disso, uviz ∈ L para i ≥ 0. Tem-se um absurdo, pois |uv| ≤ n, uv é composto 
só por a’s. Por exemplo, uv
2
z ∉ L, pois não possui o mesmo número de a’s e b’s. Logo 
L não é linguagem regular. 
 
Outros exemplos de linguagens não regulares: 
• L = {anbm | n ≤ m} 
• L = {anb2n | n ≥ 1} 
• L = {an | n é primo} 
 
Dependência. Observando os exemplos de linguagens não regulares apresentados, é 
possível notar que a quantidade de um determinado símbolo depende da quantidade de 
outro símbolo, ou ainda depende de um algoritmo que não pode ser representado 
usando um número finito de estados. 
 
Memória. Os AFDs não possuem memória. Isto é, são incapazes de armazenar a 
quantidade lida de um determinado símbolo. Nisto, reside sua principal limitação para 
reconhecer linguagens como L = {a
n
b
n 
| n ≥ 0} e L = {anbm | n ≤ m}. 
 
 
 
 
 
 
 
 
 
 
MSc. Roberto Cruz Acosta 
24 
 
 
 
16. Bibliografia 
 
LEWIS, Harry R. & PAPADIMITRION, Christos H. Elementos de Teoria da 
Computação. 2.ed. Porto Alegre, Bookman, 2000. 
 
MENEZES, Paulo Blauth. Linguagens formais e autômatos. 2.ed. Porto Alegre, Sagra 
Luzzatto, 1998. 165p. 
HOPCROFT, John E.; ULLMAN, Jeffrey D.; MOTWANI, Rajeev. Introdução à Teoria de 
Autômatos, Linguagens e Computação; Rio de Janeiro; Ed. Campus, 2002. 
 
DIVERIO, T. A.; MENEZES, P. B. Teoria da Computação: Máquinas Universais e 
Computabilidade, Série Livros Didáticos Número 5, Instituto de Informática, da 
UFRGS, Editora Sagra Luzzatto, 1a edição, 1999. 
 
EUGÊNIO, Cristiana Munhoz; PALERMO, Lilliam. Unix Avançado: Programação C- 
Shell. Disponível em http://www.ccuec.unicamp.br , acessado em 20/03/2006.