1. Construa expressão regular, gramática regular e autômato finito sobre o alfabeto {@,#,$,%}das seguintes linguagens: a) A palavra inicia com @ e...

1. Construa expressão regular, gramática regular e autômato finito sobre o alfabeto {@,#,$,%}das seguintes linguagens:
a) A palavra inicia com @ e termina com $.
b) A palavra finaliza com % ou #
c) A palavra inicia com % ou $
d) A palavra possui como subpalavra @ ou $
e) A palavra possui como prefixo @ ou $
f) A palavra possui como sufixo # ou %
g) A palavra possui como subpalavra $ ou #
h) A palavra como prefixo # ou $ ou %
2. Considere o Autômato Finito abaixo e responda:
a) Verifica se as palavras são reconhecidas pelo autômato: abbaabb e bbabababa e construir a EXPRESSÃO REGULAR e relatar se o autômato é Autômato Finito Determinístico ou Autômato Finito Não Determinístico.
b) Verifica se as palavras são reconhecidas pelo autômato: abbaab e bbababaaa e construir a EXPRESSÃO REGULAR e relatar se o autômato é Autômato Finito Determinístico ou Autômato Finito Não Determinístico.
c) Verifica se as palavras são reconhecidas pelo autômato: 10011010 e 100101 e construir a EXPRESSÃO REGULAR e relatar se o autômato é Autômato Finito Determinístico ou Autômato Finito Não Determinístico.
d) Verifica se as palavras são reconhecidas pelo autômato: 1001101 e 100100 e construir a EXPRESSÃO REGULAR e relatar se o autômato é Autômato Finito Determinístico ou Autômato Finito Não Determinístico.
3. Escreva a expressão regular dos autômatos abaixo:
a.
b.
c.
d.
e.
f. as seguintes entrada do Autômato de Pilha
a. 012210
b. 22
c. 01022001
d. 01022010
6. Considere a seguinte máquina de Turing:
Indique o traço de execução para cada uma das seguintes cadeias de entrada:
(i) aaa (ii) aba (iii) baaba