Teoria da computação

Universidade Estadual do Piauí – UESPI

Centro de Tecnologia e Urbanismo – CTU

Bacharelado em Ciência da Computação

Teoria da Computação

Prof. Tarcísio

LINGUAGENS LIVRES DE CONTEXTO

Leonardo Pedro de Sousa – 1018399

Teresina, dezembro de 2010

Linguagens Livres de Contexto

1. Gramáticas Livres de Contexto

As gramáticas livres de contexto materializam um completo entendimento do procedimento de construção das cadeias pertencentes a uma linguagem. Considerando, por exemplo, a linguagem gerada por a(a* U b*), podemos notar que qualquer cadeia dessa linguagem consiste de um a inicial, seguido por uma parte intermediária - gerada por (a* U *b) – seguido por um b final. Definindo S como um novo símbolo que pode ser interpretado como “qualquer cadeia da linguagem”, então podemos expressar essa observação escrevendo

S -> aMb

Onde -> é lido “pode ser”. Uma expressão assim construída denomina-se regra. O que pode ser M, a parte intermediária? A resposta é: ou uma cadeia de a’s, ou uma cadeia de b’s. podemos expressar esse fato adicionando as regras

M -> A

M -> B

Onde A e B são novos símbolos que representam, respectivamente, uma cadeia de a’s ou b’s. A cadeia de a’s pode ser vazia

A -> ε

ou pode consistir de um a inicial seguido por uma outra cadeia complementar de a’s

A -> AA

Analogamente, para B temos as duas regras:

B -> ε

B -> BB

A linguagem denotada pela expressão regular a(a* ∪ b*) pode, então, ser definida pela seguinte linguagem geradora: “Inicie com a cadeia elementar formada apenas pelo símbolo S. Localize um símbolo na cadeia atual, que aparece à esquerda do símbolo -> em qualquer das regras acima. Substitua uma ocorrência desse símbolo pela cadeia que aparece à direita de -> na mesma regra. Repita esse processo até que tal símbolo não possa mais ser encontrado.”

Por exemplo, para gerar a cadeia aaab, começamos com S, como especificado; então substituímos S por aMb, de acordo com a