Linguagens Formais e Autômatos

Prévia do material em texto

Universidade do Estado de Mato Grosso – UNEMAT - Campus Regional de Alto Araguaia
Departamento de Computação
Discente ________________________________________________________________ data____/____/16
Docente: Toni Amorim de Oliveira
Prova de Linguagens Formais e Autômatos
1) Como é composta a hierarquia de Chomsky
2) Defina relação 
Uma relação (binaria) é um subconjunto de um produto cartesiano. Um elemento (a,b) ϵ R, é usualmente denotado por a R b, sendo R a relação entre o domínio e o contradomínio, tal que seja conjuntos finito, não vazio de símbolos.
Uma relação R 
3) Defina alfabeto
Denotado por ∑, um alfabeto é um conjunto finito de símbolos. Um conjunto vazio também é considerado um alfabeto. Letras e dígitos são exemplos de símbolos.
4) Defina palavra, cadeia de caracteres
Símbolo (ou caractere) é uma entidade abstrata básica a qual não é definida formalmente. Uma palavra, cadeia de caracteres ou sentença sobre um alfabeto é uma sequencia finita de símbolos (do alfabeto) justapostos, símbolos frequentemente usados são, letras e dígitos.
A palavra vazia (palavra sem símbolo) é representada por Ꜫ, se ∑ representa um alfabeto, ∑* denota o conjunto de todas as palavras possíveis sobre ∑. Analogamente, ∑+ representa o conjunto de todas as palavras sobre ∑ excetuando-se a palavra vazia, ou seja, ∑+ = ∑* - {Ꜫ}
5) Defina tamanho e comprimento de uma palavra 
O tamanho ou comprimento de uma palavra W representado por |W|, é o número de símbolos que compõem a palavra. Ex: |abcb| = 4; |a| = 1; |Ꜫ| = 0.
6) Defina linguagem Formal 
Uma linguagem formal é um conjunto de palavras sobre um alfabeto. Suponha o alfabeto ∑= {a,b}. Então: O conjunto vazio e o conjunto formado pela palavra vazia são linguagens sobre ∑, tal que, {} != {Ꜫ}; O conjunto de palindromes (palavras que tem a mesma leitura da direita para a esquerda e vice-versa) sobre ∑ é um exemplo de linguagem infinita. Assim, Ꜫ, a, b, aa, bb, aaa, aba, bab, bbb, aaaa, ..., são palavras desta linguagem.
7) Suponha o alfabeto ∑= {a,b}. Então apresente as linguagens possíveis 
∑(a,b) = {Ꜫ, a, b, ab, ba, aa, bb, aba, abb, aab, aaa, bbb, baa, bba, abbb, ...}
8) Defina Concatenação
A concatenação é uma palavra binaria, definida sobre uma linguagem, a qual associa a cada par de palavras uma palavra formada pela justaposição da primeira com a segunda. Uma concatenação é denotada pela justaposição dos símbolos que representam as palavras compostas.
Associatividade: v(wt) = (vw)t.
Elemento neutro: ꜪW = W = WꜪ.
Concatenação sucessiva: CASO 1: W° = 0; W^(n) = W^(n-1)w para n >0.
CASO 2: W^(n) = Ꜫ, para n > 0; W^(n) é indefinida para n = 0;W³ = www
9) Concatene os dois alfabetos A={a,b,c} B={d,e,f}
10) Defina gramática 
11) Defina sistema de estados finitos 
12) Defina autômatos finitos
13) Defina Fita 
14) Defina unidade de controle
15) Defina função de transição