Considere a seguinte gramática G, onde S é o símbolo inicial:
S → AcB
A → cA | aB
B → cB | aA
A → λ
Assinale a alternativa que apresenta a palavra que NÃO pertence à linguagem gerada pela gramática G.
aaca
aaaca
ccca
ccac
aa
S → AcB
A → cA | aB
B → cB | aA
A → λ
Assinale a alternativa que apresenta a palavra que NÃO pertence à linguagem gerada pela gramática G.
aaca
aaaca
ccca
ccac
aa
Respostas
Ed 
há 2 anos
A palavra que não pertence à linguagem gerada pela gramática G é "ccac". Para gerar a palavra "ccac", a gramática G precisaria seguir a seguinte derivação: S → AcB → cAcB → ccAcB → ccaBc → ccac No entanto, a gramática G não gera a palavra "ccac" porque não há nenhuma regra que permita a derivação de "Bc".
Crie sua conta grátis para liberar essa resposta. 🤩
Já tem uma conta?
Ao continuar, você aceita os Termos de Uso e Política de Privacidade
Ainda com dúvidas?
Envie uma pergunta e tenha sua dúvida de estudo respondida!
Mais perguntas desse material
Considere os seguintes problemas de decisão: P1: Uma determinada máquina de estado �nito aceita uma determinada cadeia. P2: Uma determinada gramática livre de contexto gera um número in�nito de cadeias. Qual das seguintes a�rmações é verdadeira?
Apenas P2 é decidível.
P1 e P2 não são problemas de decisão.
Apenas P1 é decidível.
Ambos P1 e P2 são decidíveis.
Nem P1 nem P2 são decidíveis.
Mais conteúdos dessa disciplina
Mapa Mental - Linguagens Livres de Contexto- aula 4 - Automato de Pilhas
- Análise de Algoritmos e Computabilidade
- Teste_ Atividade Objetiva 3 2 tentativa
- 02f0204b-22f1-4207-9348-d55e253002fb
- ca540137-363c-4bfa-bf79-ce8c85350a16
- Ling Formais e Autômatos_Teste_ AO2
- Videoaula 8 - Gramáticas
- SIMULADO 2
- Se é o código da máquina de Turing , definimos as linguagens é regular e é livre de contexto .Assinale a alternativa verdadeira.Alternativas:a) e são
- Considere a seguinte gramática livre de contexto :;;Considere que você sabe que a linguagem das cadeias não é livre de contexto, .Sobre a linguagem ge
- Se é o código da máquina de Turing , definimos as linguagens é regular e é livre de contexto . Assinale a alternativa verdadeira. Alternativas: a) e s
- Considere o AFD definido pela seguinte tabela: 0 1 *q0 q1 q1 q1 q0 q1 onde o estado inicial é marcado com a seta "" e os estados finais marcados com "
- Uma linguagem é um conjunto, finito ou infinito, de cadeias de comprimento finito, formadas pela concatenação de elementos de um alfabeto finito e não
- CONSIDERE OS CONJUNTOS A= {2,4,6,8,10,16,20} e B {2,4,8,10,16}
Escolha uma: a. {2, 4, 6, 8} b. {6, 10, 16} c. {2, 6, 8, 12} d. {10, 12} e. {6, 12...
- Uma técnica foi encarregada da instalação elétrica de máquinas com diferentes correntes elétricas. Para agilizar 0 trabalho, escolheu utilizar cone...
- As imagens a seguir, extraídas da questão 180 do ENEM 2023, da área de Matemática e suas tecnologias, disponível no link a seguir: https://youtu.be/Ic
- 4) Considere o AFD definido pela seguinte tabela: 0 1 *90 q₁ q₁ q₁ 90 q₁ onde o estado inicial é marcado com a seta "-" e os estados finais marcados c
- 3) Uma linguagem é um conjunto, finito ou infinito, de cadeias de comprimento finito, formadas pela concatenação de elementos de um alfabeto finito e
- Uma linguagem é um conjunto, finito ou infinito, de cadeias de comprimento finito, formadas pela concatenação de elementos de um alfabeto finito e não
- Considere a gramática onde: ; ; Marque a cadeia gerada pela gramática G: Selecione uma alternativa: a) 1110111 b) 1111001 c) 1111011 d) 1111100 e) 111
- (IFB/2017/PROFESSOR/INFORMÁTICA) Considerando-se a definição de autômatos finitos, assinale a única alternativa que contém somente cadeias de carac...
- NoSQL - 1 Apostila Módulo 3
- ciência da computação