Teoria da Computação - Questões Resolvidas sobre Gramáticas, Autômatos e Linguagens Formais

Qual das gramáticas gera a linguagem an bn cm dm para n 0 e m 0 A B C a b c d A aBbC B aBb C cCd B ab C cd A A B C a b c d A BC B aBb C cCd B ab C cd A A B C a b c d A B A CB B aBb C cCd B ab C cd A A B C a b c d A B A BC B aBb C cCd B ab C cd A A B C a b c d A CB B aBb C cCd B ab C cd A Qual das linguagens é reconhecida pelo autômato abaixo 0n 11 0n para n 0 0n 1 U 11 0n para n 0 0n 1 U 11 0n para n 0 0n 11 0m para n 0 m 0 0n 1 0n para n 0 Qual expressão regular gera a mesma linguagem que a GLC S A B x y S AB S BA B x A yA A E S A E corresponde à variável A substituída pela string vazia y x y x y x y U x x y U y x y x y Qual das seguintes LLCs não é regular xn para n 0 x yn para n 0 xn y xn para n 0 xn y xm para n 0 m 0 xyn para n 0 Considere um ACP que reconhece a linguagem an bm cm dn n 0 m 0 Qual a quantidade máxima de elementos na pilha desse ACP para a verificação de uma string que pertence à linguagem n m 1 m 1 3 n 1 maxn m 1 Considere os conjuntos de regras de substituição abaixo com o conjunto de variáveis S A B e o alfabeto a b c Qual dos conjuntos é passível de apresentar ambiguidade S bA S aB A aA A c B bB B c S A S B A aA A c B bB B c S A S B A aAa A c B bBb B c S A S B A AaA A c B BbB B c S A S B A BaA A c B AbB B c Qual das GLCs gera a linguagem reconhecida pelo ACP a seguir S 0 1 S 0S0 S 11 S S 0 1 S 0S1 S 11 S S 0 1 S 0S0 S 11 S 1 S S 0 1 S 0S1 S 1 S S 0 1 S 0S0 S 1 S Considere um ACP que reconhece a linguagem an bm cn n 0 m 0 Qual a quantidade máxima de elementos na pilha desse ACP para a verificação de uma string que pertence à linguagem n m 1 m 1 maxn m 1 n 1 3 Questão 1 Item d Questão 2 Item a Questão 3 Item d Questão 4 Item c Questão 5 Item a Questão 6 Item e Questão 7 Item a Questão 8 Item d Questão 1 Item d Questão 2 Item a Questão 3 Item d Questão 4 Item c Questão 5 Item a Questão 6 Item e Questão 7 Item a Questão 8 Item d