Exercicio automato

Exercicio automato

Teoria das Linguagens e dos Autómatos

Exercícios – Expressões Regulares

1-

Sejao alfabeto.

Escreva e

O alfabeto é finito.

O conjunto de todas as palavras geradas é infinito.

Há linguagens finitas como

E linguagens infinitas como

O complemento de uma linguagem é dado por

2-

Seja . Quais das seguintes palavras pertencem à linguagem ?

abaabaaaabaa ab aa baa aa baa sim

aaaabaaaa aa aa baa aa sim

baaaaabaaaab baa aa ab aa aa b não

baaaaabaa baa aa ab aa sim

3-

Utilizando a seguinte Linguagem, construa um conjunto de palavras válidas na língua portuguesa, através de prefixos e sufixos.

4-

Se escreva

simplificando

5-

O DNA de todos os seres vivos é constituído por Adenina, Guanina, Timina e Citosina. O RNA contém Uracilo em vez de Timina.

a) Sabendo que os aminoácidos são constituídos por uma sequência de 3 moléculas do conjunto seguida de uma outra molécula X, e que as sequências de início pertencem ao conjunto e as de fim ao conjunto, produza uma expressão regular que permita gerar casos possíveis como por exemplo:

AUGUACXGCAXCAAXUGA

b) Sabendo que o processo de duplicação da cadeia de DNA utiliza as sequências TTGACA e a TATAAT como marcas de início e de fim, produza uma expressão regular que identifique uma sequência em processo de duplicação.

Exercícios – Gramáticas

Seja uma gramática com alfabeto (conjunto finito de símbolos terminais), e com um conjunto finito de símbolos não terminais (variáveis) resultante da derivação do conjunto finito de produções sobre o alfabeto tendo como variável inicial.

Então é a linguagem gerada por

Eé uma palavra dessa linguagem produzida do seguinte modo:

1- Construa as gramáticas que tendo como alfabeto gere

  1. todas as palavras com apenas um b

  2. todas as palavras com pelo menos um b

  3. todas as palavras no máximo com 3 b

  4. todas as palavras com pelo menos 3 b

2- Escreva a linguagem gerada com uma gramática com as seguintes produções:

a)

b)

3- Escreva a Gramática que gera as seguintes linguagens:

a)

b)

c)

d)

e)

f)

g)

h)

i)

4- Escreva 3 palavras diferentes através da gramática com as produções

Autor Original: Vítor Vaz da Silva 3

Comentários