O que é alfabeto

Prévia do material em texto

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”, de qualquer tamanho, mais 
a cadeia nula (λ). 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? 
 6. Fale sobre aplicações de LFA. É difícil descrever todo o universo de aplicações nas quais se 
pode utilizar os modelos estudados em LFA. Entretanto, entre as principais aplicações, podese 
destacar: • análise de linguagens de programação o léxica; o sintática; • modelos de sistemas 
biológicos; • desenho de hardware; • relacionamentos com linguagens naturais; • 
processamento de imagens ou visão computacional (reconhecimento de padrões); 
 
 
 7. Defina o conceito de subpalavra. Dadas x e y, cadeias pertencentes à Σ*. Uma cadeia x é 
uma subpalavra de uma cadeia y sse ∃w,u ∈ Σ* tal que y= 
 
8. Dados L1={a, ab} e L2={λ, a, ba}, linguagens sobre Σ={a, b}, determine: 
a. L1 ∪ L2 = {a, ab, λ, ba} 
b. L1 ∩ L2 = {a} 
c. L1 – L2 = {ab} 
d. L2 – L1 = {λ, ba} 
e. L1.L2 = {a, aa, aba, ab, abba} 
f. L2.L1 = {a, ab, aa, aab, baa, baab} 
g. L1 2 = L1.L1 = {aa, aab, aba, abab} 
h. L2 2 = L2.L2 = {λ, a, ba, aa, aba, baa, baba} 
i. L1 = Σ * - L1 = {a, b} * - {a, ab} 
 
1) Elabore um autômato finito determinístico que aceita a linguagem sobre o alfabeto {0,1} tal 
que as palavras apresentem a seqüência 01 em qualquer posição, ou seja, L = {x01y | x,y ∈ 
{0,1}*} 
 
 
2) Construa um autômato finito determinístico sobre o alfabeto {0.1} que aceite todas as 
palavras terminadas em 00. 
 
3) Construa AFDs (Autômatos Finitos Determinísticos) que reconheçam as linguagens abaixo: 
a) L1 = {w | w ∈ {0,1}* e w começa por 1 e termina por 0} 
b) L2 = {w | w ∈ {0,1}+ } 
c) L3 = {w | w ∈ {0,1}* e |w| 3} 
 
 
4) Descreva um AFD capaz de reconhecer somente datas válidas (não levando em 
consideração anos bissextos) no formato americano mês/dia, onde mês e dia são 
representados com dois dígitos. 
 
 
5) Utilizando a ferramenta JFLAP (http://www.cs.duke.edu/~rodger/tools/tools.html), 
implemente e teste todos os autômatos desenvolvidos nas questões anteriores. 
6) Descreva com suas palavras a linguagem reconhecida pelo seguinte autômato: L