Ling Formais e Autômato

Prévia do material em texto

Linguagens Formais e Autômatos Prof. Roberto Luís M. P. de Castro 
Atividade Individual Avaliativa - A1 Página:(nº da página) 
Turma: 1INF12A Data da entrega: 22/ 04/ 2021 
Aluno: Isabella Coimbra Garcia Portella 
Aluno: Mariana Rodrigues de Souza 
Aluno: Clara Pessoa Teixeira 
ATIVIDADES 
------------------------------------------------------------------------------------------------------------------------ 
 
Atividade 01: 
 
Letra D. 
 
I - Errada. 
Justificativa: Pois na alternativa está que a linguagem natural é criada por pessoas mais espontâneas, 
enquanto as linguagens formais são criadas por pessoas mais rígidas. A criação dessas desses dois 
tipos de linguagens não tem a ver com a pessoa ser mais espontânea ou não, e sim se a linguagem foi 
feita para a comunicação do homem com a máquina ou entre dois seres humanos. 
 
II - Certa. 
Justificativa: A linguagem natural é o principal meio de comunicação e o mais comum entre os seres 
humanos, alguns exemplos dessa linguagem são os idiomas, como o inglês, francês e português. 
Enquanto, a linguagem formal são mecanismos formais para representação e especificação de 
linguagens, baseados na chamada "Teoria da Computação”. 
 
III - Errada. 
Justificativa: Pois, diz que uma Linguagem natural permite, a comunicação entre homem e máquina 
de forma espontânea, no entanto, quem faz esse papel é a linguagem formal, pois na linguagem natural 
a comunicação ocorre entre dois seres humanos. 
 
IV - Certa. 
Justificativa: A linguagem formal é definida abstratamente como um sistema matemático, os quais 
nos permitem realizar rigorosas declarações sobre elas e desenvolver um corpo de conhecimento que 
pode então ser aplicado àquelas linguagens que são modeladas convenientemente. Enquanto, a 
linguagem natural é uma expressão de cultura de um grupo em seu significado mais puro, com isso, 
os seres humanos, por sua vez, transmitem a linguagem através do aprendizado. 
 
Atividade 02: 
 
Letra C. 
 
I - Certa. 
Justificativa: Pois G é uma gramática regular e a gramática linear que corresponde a ela é uma 
Gramática Linear Unitária à direita, já que de acordo com as regras, todos os símbolos não terminais 
do lado direito da regra estão do lado direito dos outros símbolos. 
 
II - Errada. 
Justificativa: Pois a gramática unitária a direita não tem regras de produção como, A —>Bw, e sim 
A —> wB. 
 
III - Certa. 
Justificativa: Pois, como na alternativa I, tem-se que G é uma gramática regular e uma Gramática 
Linear Unitária à direita. A linguagem L = {a(ˆn)ba(ˆm) | n, m > 0} é a linguagem gerada pela 
gramática, já que um exemplo é aabaaa (1. S —> aS, 2. aA, A —> bD, 3. D —> aD | a, utilizando 
Linguagens Formais e Autômatos Prof. Roberto Luís M. P. de Castro 
Atividade Individual Avaliativa - A1 Página:(nº da página) 
Turma: 1INF12A Data da entrega: 22/ 04/ 2021 
Aluno: Isabella Coimbra Garcia Portella 
Aluno: Mariana Rodrigues de Souza 
Aluno: Clara Pessoa Teixeira 
ATIVIDADES 
------------------------------------------------------------------------------------------------------------------------ 
essas regras a palavra DAD —> regra 3 —> aDAD —> regra 3 —> aaAD —> regra 2 —> aabD —
> regra 3 —> aabaD —> regra 3 —> aabaaD —> regra 3 —> aabaaa). 
 
IV - Errada. 
Justificativa: Pois G é uma gramática regula, no entanto não é uma Gramática Linear Unitária à 
esquerda, e sim, à direita, já que todos os símbolos não terminais do lado direito da regra estão do 
lado direito dos outros símbolos. 
 
Atividade 03: 
 
Letra A. 
 
I - Errada. 
Justificativa: Pois tem-se as seguintes regras, P = { N —> D, N —> DN, D —> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 
7 | 8 | 9}, assim para permitir 0 à esquerda e ser uma gramática linear unitária à esquerda, A —> Bw 
e A —-> w, sendo V = {A, B} e T = {w}, que aplicados ao exemplo do exercício, temos que V = 
{N,D} e T = {0, 1,2, 3, 4, 5, 6, 7, 8, 9}. No entanto, como a regra é A —> Bw, isso colocaria os 0 à 
direita e não à esquerda. 
 
II - Certa. 
Justificativa: Pois os símbolos *, + e 6, significam respectivamente, deriva em zero ou mais passos 
sucessivos, deriva em um ou mais passos sucessivos e deriva em 6 passos sucessivos. Com isso, o 
número 567, pode ter como exemplo: DN —> 5N —> 5DN —> 56N —> 56D —> 567. 
 
III - Errada. 
Justificativa: Pois as regras são P = { S —> DS, D —> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9}, isso faz com 
que uma palavra que contenha DS, sempre ficará com o S contido na palavra. 
 
IV. Certa. 
Justificativa: Pois a alternativa diz que são sufixos da palavra 12345: 1, 12, 123, 1234, 12345, 
sabendo-se que sufixo de uma palavra é qualquer sequência de símbolos finais da palavra. 
 
Atividade 04: 
 
Letra C. Pois tanto o Tipo 2 quanto o Tipo 3 tem como reconhecedor os autômatos à pilha e autômatos 
finitos, respectivamente. Já a classe Tipo 1 tem como reconhecedor a Máquina de Turing com 
memória limitada e a do Tipo 0, tem como reconhecedor a Máquina de Turing. 
 
 
Atividade 05: 
 
A. De acordo com a Hierarquia Chomsky, a gramática é uma GLC, gramática livre de contexto, 
Tipo 2 e tem por característica a presença de somente uma variavél não-terminal do lado 
esquerdo. 
B. L(G)= {ww^r : ∈ {a,b}*} ou L(G)= {a^nba^a | n>0} 
C. i. S → aS → aSb → aabb 
ii. S → Sb → aSb → aabb 
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
Linguagens Formais e Autômatos Prof. Roberto Luís M. P. de Castro 
Atividade Individual Avaliativa - A1 Página:(nº da página) 
Turma: 1INF12A Data da entrega: 22/ 04/ 2021 
Aluno: Isabella Coimbra Garcia Portella 
Aluno: Mariana Rodrigues de Souza 
Aluno: Clara Pessoa Teixeira 
ATIVIDADES 
------------------------------------------------------------------------------------------------------------------------ 
D. i. ii. 
 
 
 
 
 
 
 
 
 
 
 
Atividade 06: 
 
A. Formalismo: ({0,1}, {S0, S1, Sf }, , S0, { Sf }) 
 
B. Tabela de Transição: 
 
 
 
 
 
 
 
 
 
C. Tabela de Transição na forma de função: 
( S0, 0) = S1 ( S1, 1) = Sf ( Sf, 1) = Sf 
( S1, 0) = S1 ( Sf , 0) = S1 
 
D. Verificar se “0000111100” pertence L(M) 
 
S0 ->
0 S1 ->
0 S1 ->
0 S1 ->
0 S1 ->
1 Sf ->
1 Sf ->
1 Sf ->
1 Sf ->
0 S1 ->
0 
 
Resposta: Temos que após processar o último símbolo da palavra, o autômato assume um estado 
não-final e para, então a palavra “0000111100” não pertence a L(M). 
 
Atividade 07: 
 
A. Formalismo: ({0,1}, {q0, q1, q2 }, , q0, { q1, q2 }) 
 
 
 
 
 
 
 0 1 
S0 S1 - 
S1 S1 Sf 
Sf S1 Sf 
 S 
 
a S 
 
 
 S b 
 
 
 a b 
S 
 
 S b 
 
 
a S 
 
 
 a b 
Linguagens Formais e Autômatos Prof. Roberto Luís M. P. de Castro 
Atividade Individual Avaliativa - A1Página:(nº da página) 
Turma: 1INF12A Data da entrega: 22/ 04/ 2021 
Aluno: Isabella Coimbra Garcia Portella 
Aluno: Mariana Rodrigues de Souza 
Aluno: Clara Pessoa Teixeira 
ATIVIDADES 
------------------------------------------------------------------------------------------------------------------------ 
B. Representação em forma de grafo: 
 0 
 
 1 0 
 
 
 
 0 1 0 
 
C. Tabela de Transição na forma de função: 
 
 
 
 
D. Verificar se “0111” pertence L(A) 
 
 0 
 
 
 
 1 1 1 
 
 
Resposta: Temos que após processar o último símbolo da palavra, o autômato assuma um estado final 
e para, então a palavra “0111” pertence a L(A). 
 
Atividade 08: 
 
A. S → aA → abD → abaD → abaa 
 
 
B. Sim, se uma linguagem é regular, logo existe G, uma gramática regular que gera L. Nesse 
caso, trata-se de uma Gramática Linear Unitária à Direita, já que todas as variáveis não-
terminais estão a direita dos terminais. 
 
C. S → aS → aaA → aabD → aabaD → aabaaD → aabaaa 
 
 
D. Árvore de derivação: 
(professor, para a melhor visualização da árvore de derivação da 
Palavra “aabaaa”, a figura está ao lado →) 
 
 
 
 
 
 
( q0, 0) = q0, q2 ( q1, 0) = q2 ( q2, 0) = q2 
( q0, 1) = q1 ( q1, 1) = q1 
q0 q1 q2 
q0 q2 
q0 q1 q1 q1 
 aA bD aD aD a 
 bD aD a 
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92
https://coolsymbol.com/copy/Rightwards_Arrow_Symbol_%E2%86%92