Logo Passei Direto
Buscar
POSCOMP / 2009 Qual é a linguagem da gramática com as seguintes regras de produção: S → ASb | c A → a
Assinale a alternativa correta.
{a^n cb | n ∈ N}
{acb^n | n ∈ N}
{a^n c^n b | n ∈ N}
{a^n cb^n | n ∈ N}
{ac^n b | n ∈ N}
User badge image
Praticando Para o Saber

há 3 meses

Respostas

User badge image

Ed Verified user icon

há 3 meses

Vamos analisar a gramática dada: Regras: S → ASb | c A → a Passo 1: Entender A A → a, ou seja, A gera exatamente um 'a'. Passo 2: Analisar S → ASb | c - Se S → c, a cadeia gerada é simplesmente "c". - Se S → ASb, substituindo A por 'a', temos: S → aSb. Isso indica que a produção S → aSb é recursiva, gerando cadeias com 'a' no início, 'b' no final, e um 'c' no meio (pois a recursão termina quando S → c). Passo 3: Gerar cadeias - Para n=0 (zero recursões): S → c - Para n=1: S → a S b → a c b - Para n=2: S → a S b → a (a S b) b → a a c b b - Para n=n: a^n c b^n Portanto, a linguagem gerada é: { a^n c b^n | n ∈ N } Resposta correta: {a^n c b^n | n ∈ N} Alternativa correta: d) {a^n cb^n | n ∈ N}

Essa resposta te ajudou?

0
Dislike0

Ainda não achou a resposta?

  • Integrado com os principais modelos de IA do mercado
  • Respostas em segundos
  • IA treinada para estudantes brasileiros.
PasseIA logoEvolua sua forma de estudar

Cadastre-se ou realize login

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Mais perguntas desse material

A linguagem gerada pelo GLC é chamada de linguagem livre de contexto (LLC). Acerca de suas características, a linguagem livre de contexto não é fechada em relação a:
Divisão.
Complementação.
Concatenação.
Fechamento de Kleene.
União.

Considere os seguintes problemas de decisão: P1: Uma determinada máquina de estado finito aceita uma determinada cadeia. P2: Uma determinada gramática livre de contexto gera um número infinito de cadeias.
Qual das seguintes afirmacoes é verdadeira?
P1 e P2 não são problemas de decisão.
Ambos P1 e P2 são decidíveis.
Apenas P1 é decidível.
Nem P1 nem P2 são decidíveis.
Apenas P2 é decidível.

Mais conteúdos dessa disciplina