Conceitos Básicos de LFA

Lista de Exercícios no 1 – Conceitos Básicos de LFA
1. O que é alfabeto?

Alfabeto é um conjunto finito e não vazio de símbolos. Geralmente, o alfabeto é denotado por ∑. Um exemplo de alfabeto seria ∑ = {0, 1}, ou seja, um alfabeto que possui dois símbolos, “0” e “1”.
2. Defina o conceito de cadeia.

Uma cadeia é uma seqüência formada por símbolos pertencentes à um mesmo alfabeto. Por exemplo, a partir do alfabeto ∑ = {0, 1} seria possível formar as cadeias 0, 001 e 110101. Note que diferentes cadeias não precisam necessariamente ter a mesma quantidade de símbolos.
3. Defina o conceito de linguagem e mostre um exemplo.

Linguagem é um conjunto de cadeias formadas a partir de um mesmo alfabeto. Assim, L = {0, 1, 00, 01, 10, 11} seria um exemplo de linguagem formada a partir do alfabeto ∑ = {0, 1}. A quantidade de cadeias pertences à uma linguagem não é necessariamente finita.
4. O que é fechamento de um alfabeto?

Fechamento de um alfabeto é o conjunto de todas as cadeias possíveis de se formar a partir dos símbolos deste alfabeto. Denota-se o fechamento de um alfabeto ∑ por ∑*. Para o alfabeto ∑ = {1}, por exemplo, ∑* seria formado por todas as seqüências possíveis do símbolo “1”, mais a cadeia nula (λ), de qualquer tamanho. Pode-se notar que, basta que o alfabeto possua um único símbolo (conjunto não vazio) para que o seu fechamento seja infinito.
5. Como se pode descrever uma linguagem formal?

Uma linguagem formal pode ser descrita por um modelo reconhecedor ou por um modelo gerador. Um modelo reconhecedor é um modelo matemático capaz de percorrer (“varrer”) uma cadeia de símbolos construída a partir de um alfabeto e, ao final desta “varredura”, identificar se esta cadeia faz parte

ou não da linguagem descrita por ele. Neste contexto, a linguagem descrita pelo modelo corresponde ao conjunto formado por todas as cadeias que ele aceita. Já um modelo gerador é um modelo capaz de gerar (produzir) as cadeias que fazem parte de