1

Teoria da Computação e Compilação

Prof. Cícero C. Quartocicero@engcomp.uema.brhttp://www.engcomp.uema.br

Engenharia de Computação

Os conceitos centrais da teoria de autômatos

Nessa seção, introduziremos as definições mais importantes dos termos que permeiam a teoria de autômatos.

• Esses conceitos incluem o “alfabeto” (um conjunto de símbolos), “strings” (uma lista de símbolos de um alfabeto) e “linguagem” (um conjunto de strings de um mesmo alfabeto).

Alfabetos

Um alfabeto é um conjunto de símbolos finito e não-vazio. Convencionalmente, usamos o símbolo Ʃ para um alfabeto. Os alfabetos comuns incluem:

1. Ʃ = {0,1}, o alfabeto binário.2. Ʃ = {a, b, ..., z}, o conjunto de

todas as letras minúsculas.3. O conjunto de todos os caracteres

ASCII, ou o conjunto de todos os caracteres ASCII imprimíveis.

2

Strings

Um string (ou às vezes palavra ou também cadeia) é uma sequência finita de símbolos escolhidos de algum alfabeto.

Exemplo: 01101 é um string do alfabeto binárioƩ = {0,1}. O string 111 é outro string escolhido nesse alfabeto.

O string vazioO string vazio é o string com zero

ocorrências de símbolos. Esse string, denotado por Ɛ, é um string que pode ser escolhido de qualquer alfabeto.

Comprimento de um stringCom frequência, é útil para classificar strings por

seu comprimento, isto é, o número de posições para símbolos no string.

Exemplo: 01101 tem comprimento 5Observação

É comum dizer que o comprimento de um string é o “número de símbolos” no string; essa afirmação é coloquialmente aceita, mas não é estritamente correta. Desta forma, existem só dois símbolos, 0 e 1, no string 01101, mas existem cinco posições para símbolos, e seu comprimento é 5.

Em geral, devemos esperar que o “número de símbolos” possa ser usado quando o significado for “número de posições”.

A notação padrão para o comprimento de um string w é |w|.

Exemplo: |011| = 3 e |Ɛ| = 0

Potências de um alfabetoSe Ʃ é um alfabeto, podemos expressar o conjunto

de todos os strings de um certo comprimento a parte desse alfabeto, usando uma notação exponencial.

Definimos Ʃk como o conjunto de strings de comprimento k, e o símbolo de cada um deles está em Ʃ.

Exemplo: Observe que Ʃ0 = {Ɛ}, independente de qual alfabeto seja Ʃ. Isto é, Ɛ é o único string cujo comprimento é 0.

Se Ʃ = {0, 1}, então Ʃ1 = {0, 1}, Ʃ2 = {00, 01, 10, 11},

Ʃ3 = {000, 001, 010, 011, 100, 101, 110, 111}e assim por diante.

3

Observe que existe uma ligeira confusão entre Ʃ e Ʃ1. O primeiro é um alfabeto; seus elementos 0 e 1 são símbolos. O outro é um conjunto de strings; seus elementos são os strings 0 e 1, cada um dos quais tem comprimento 1.

O conjunto de todos os strings sobre um alfabeto Ʃ é denotado convencionalmente por Ʃ*

Exemplo: {0,1}* = {Ɛ, 0, 1, 00, 01, 10, 11, 000, ...}. Em outros termos,

Ʃ* = Ʃ0⋃Ʃ1⋃Ʃ2⋃...

Às vezes, desejamos excluir o string vazio do conjunto de strings. O conjunto de strings não vazios do alfabeto Ʃ é denotado por Ʃ*. Desse modo, duas equivalências apropriadas são:

• Ʃ+ = Ʃ1⋃Ʃ2⋃...• Ʃ* = Ʃ+⋃{Ɛ}

Concatenação de stringsSejam os strings x e y. Então, xy denota a

concatenação de x e y, isto é, o string formado tomando-se uma cópia de x e acrescentando-se a ela uma cópia de y.

Mais precisamente, se x é o string composto de i símbolos x = a1a2 ... ai e y é o string composto de j símbolos y = b1b2 ... bj, então xy é o string de comprimento i + j: xy = a1a2 ... aib1b2 ... bj

Exemplo: Sejam x = 01101 e y = 110. Então xy = 01101110 e yx = 11001101.

Para qualquer string w, as equações Ɛw = wƐ = w são válidas. Isto é, Ɛ é a identidade para a concatenação, pois, quando é concatenado com qualquer string, ele produz o mesmo string como resultado (de forma análoga ao modo como 0, a identidade para a adição, pode ser somado a qualquer para número x e produz x como resultado).

4

Linguagens

Um conjunto de strings, todos escolhidos a partir de algum Ʃ*, onde Ʃ é um alfabeto específico, é chamado linguagem.

Se Ʃ é um alfabeto, e L � Ʃ*, então L é uma linguagem sobre Ʃ.

Linguagens comuns – conjunto de stringsExemplo: Português, no qual uma coleção de palavras válidas

é um conjunto de strings sobre o alfabeto que consite em todas as letras.

Exemplo: C, ou qualquer outra linguagem de programação, na qual os programas válidos são um subconjunto dos strings possíveis que podem ser formados a partir do alfabeto da linguagem.

Alfabeto: letras maiúsculas e minúsculas, dígitos, pontuação e símbolos matemáticos

Outros exemplos de linguagens:

1. A linguagem de todos os strings que consistem em n 0´s seguidos por n valores 1, para algum n ≥ 0: {�, 01, 0011, 000111, …}

2. O conjunto de strings de 0´s e 1´s com número igual de cadaum deles:

{�, 01, 10, 0011, 0101, 1001, …}3. O conjunto de números binários cujo valor é um número primo:

{10, 11, 101, 111, 1011, …}4. Ʃ* é uma linguagem para qualquer alfabeto Ʃ.5. φ, a linguagem vazia, é uma linguagem sobre qualquer alfabeto.6. {ε}, a linguagem que consiste apenas no string vazio, também é

uma linguagem sobre qualquer alfabeto. Note que � ≠ {�}: o primeiro não tem nenhum string, enquanto o outro tem um únicostring.

Problemas

Na teoria de autômatos, um problema é a questão de decidir se um dado string é elemento de alguma linguagem específica. Mais precisamente, se Ʃ é um alfabeto e L é uma linguagem sobre Ʃ, entãoo problema L é:

Dado um string w em Ʃ*, definir se w está ou não em L.

Exemplo: O problema de testar o caráter primo pode ser expressopela linguagem Lp que consiste em todos os strings binários cujovalor como um número binário é primo. Ou seja, dado um string de 0´s e 1´s, diremos “sim” se o string for a representação binária de um primo e diremos “não” se não for.

Por exemplo, 0011101 pode ser a representação de um primo, pela simples razãode que todo inteiro, exceto 0, tem uma representação binária que começa com 1. Entretanto, é menos óbvio se o string 11101 pertence a Lp, e assim qualquer solução paraesse problema terá de usar recursos computacionais significativos de algum tipo: tempo e/ou espaço, por exemplo.

5

Formadores de conjuntos como

um modelo de definir linguagens

É comum descrever uma linguagem usando um “formador de conjuntos”:

{w |algo sobre w}

Essa expressão é lida como “o conjunto de palavras w tais que (sejao que for dito sobre w à direita da barra vertical)”.

Exemplos:

1. {w | w consiste em um número igual de 0´s e 1´s}2. {w | w é um número inteiro binário primo}3. {w | w é um programa em C sintaticamente correto}

Também é comum substituir w por alguma expressão com parãmetros e descrever os strings na linguagem declarando condições sobre os parâmetros. Aqui estão alguns exemplos; o primeiro com o parâmetro n, o segundo com os parâmetros i e j:

Exemplos:

1. {0n1n | n≥1}. Lê-se “o conjunto de 0 elevado a n 1 elevado a n talque n é maior que ou igual a 1”, essa linguagem consiste nosstrings {01, 0011, 000111, …}

2. {0i1j | 0≤i≤j}. Essa linguagem consiste em strings com alguns0´s(possivelmente nenhum) seguidos por um número igual ousuperior de 1´s. Essa linguagem consiste nos strings {ε, 01, 0101, 010101, …}

Resumo do capítulo 1

� Autômatos finitos: Os autômatos finitos envolvem estados e

transições entre estados em resposta a entradas. Eles são úteis na

elaboração de vários tipos diferentes de software, inclusive o

componente de análise léxica de um compilador e sistemas para

verificar a correção de circuitos ou protocolos

� Expressões regulares: Essas expressões formam uma notação

estrutural para descrever os mesmos padrões que podem ser

representados por autômatos finitos. Elas são usadas em muitos tipos

comuns de software que incluem, por exemplo, ferramentas para

pesquisa de padrões em textos ou em nomes de arquivos

6

Resumo do capítulo 1 – cont...

� Gramáticas livres de contexto: Essas gramáticas constituem uma

notação importante para descrever a estrutura de linguagens de

programação e conjuntos de strings inter-relacionados; elas são

usadas para elaborar o componente analisador sintático de um

compilador

� Máquinas de Turing: Essas máquinas são autômatos que modelam

o poder dos computadores reais. Elas nos permitem estudar a

decidibilidade, a questão do que pode ou não ser feito por um

computador. Elas também tornam possível distinguir problemas

tratáveis – aqueles que podem ser resolvidos em tempo polinomial –

dos problemas intratáveis – aqueles que não o podem

Resumo do capítulo 1 – cont...

� Alfabetos: Um alfabeto é qualquer conjunto finito não-vazio de símbolos

� Strings: Um string é uma seqüência de comprimento finito de símbolos

� Linguagens e problemas: Uma linguagem é um (possivelmente infinito)

conjunto de strings, os quais escolhem seus símbolos a partir de algum

alfabeto único. Quando os strings de uma linguagem têm de ser

interpretados de algum modo, a questão de saber se um string pertence à

linguagem às vezes se denomina um problema