Qual é a linguagem gerada pela gramática S → aSb, S → A, A → aA? a bm m a bm n ∅ a bn m a bj i

Exercícios Para o Conhecimento

há 4 meses

Exercícios Para o Conhecimento

há 4 meses

8 pág.

Respostas

há 4 meses

A gramática dada gera a linguagem \( L = \{ a^m b^n \mid m \geq 0, n = m \} \). Isso significa que a quantidade de 'a's deve ser igual à quantidade de 'b's. Portanto, a linguagem gerada é composta por cadeias que têm a mesma quantidade de 'a's e 'b's, como \( \{ \varepsilon, ab, aabb, aaabbb, \ldots \} \). Se precisar de mais alguma coisa, é só avisar!

Essa resposta te ajudou?

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!

Essa pergunta também está no material:

8 pág.

Exercicio 3

ESTÁCIO EAD

Mais perguntas desse material

A diferença entre autômatos finitos e autômatos de pilha está na:
Pilha.
Controle finito.
Direção do movimento da cabeça de leitura.
Fita de entrada.
Cabeça de leitura.

Pilhas possuem somente uma entrada chamada de topo e são compostas por duas operações fundamentais. Sobre os conceitos de pilha, como é implementado os mecanismos de inserção/remoção?
FIFO.
FIFA.
LIFO.
FFLL.
PEPS.

Em relação a autômatos e linguagens, podemos afirmar:
I. PDA é o formato de máquina de linguagem livre de contexto.
II. A descrição instantânea do PDA descreve a configuração dele em uma determinada instância.
III. Uma cadeia de uma LLC pode ser aceita por pilha vazia ou pelo estado final.
I, II e III
II e III
I e III
II
I

Gramáticas definem linguagens, sendo especificações finitas de regras de geração de cadeias. Nesse sentido,
assinale a alternativa incorreta.
a + b denota {a} U {b} = {a, b}
V U T = Σ
λ ∈ Σ*
V ∩ T = ∅
V ∩ T = Σ*

Com base nas afirmativas abaixo assinale a resposta correta:
I. Alfabeto ou vocabulário "V" é um conjunto finito e não vazio de símbolos.
II. Uma palavra sobre o alfabeto "V" é uma cadeia de comprimento finito de símbolos de "V".
III. Gramáticas são especificações infinitas de linguagens finitas.
IV. A classe das linguagens regulares é um subconjunto próprio da classe das linguagens livres de contexto.
I, II e III, apenas.
II e IV, apenas.
I e IV, apenas.
II e III, apenas.
I, II e IV, apenas.

Uma linguagem L gerada a partir de uma dada GLC onde não existem ciclos no grafo direcionado gerado a partir das regras de produção dessa GLC, é denominada de:
Finita.
Recursiva.
Infinita.
Irrestrita (sem restrições).
Sem contexto.

Considere a seguinte propriedade sobre uma linguagem formal L: Existe um número natural n ≥ 0, tal que para qualquer palavra w ∈ L: 1. Todo z ∈ L com z ≥ n pode ser escrito como w = uvwxy, para algumas cadeias u,v,w,x,y. 2. |vx| ≥ 1 3. |vwx| ≤ n 4. uvkwxky ∈ L para todo k ≥ 0 Com base no enunciado e nos conhecimentos sobre o tema, atribua V (verdadeiro) ou F (falso) para as afirmativas a seguir.
( ) Se L é aceita por PDA, então L satisfaz a propriedade acima.
( ) L = {0 ; onde p é primo} não satisfaz a propriedade acima.
( ) A propriedade acima é falsa para a linguagem L = {WcW | W ∈ (a, b)*}
( ) A linguagem {a b c ; n ≥ 0} não satisfaz a propriedade acima.
( ) O lema do bombeamento para linguagem livre de contexto é usado para provar que certos conjuntos são livres de contexto.
V, V, V, V, F.
V, V, F, V, F.
V, F, V, F, F.
F, V, V, F, V.
F, V, F, V, V.

Avalie as proposições (1) e (2) a seguir: (1) Uma linguagem L gerada a partir de uma dada GLC é infinita (2) se houver pelo menos um ciclo no grafo direcionado gerado a partir das regras de produção dessa GLC A esse respeito, assinale a afirmativa VERDADEIRA.
As proposições (1) e (2) são verdadeiras, sendo que a (1) justifica a (2).
Ambas as proposições são falsas.
A proposição (1) é verdadeira e (2) é falsa.
As proposições (1) e (2) são verdadeiras, sendo que a (2) justifica a (1).
As proposições (1) e (2) são verdadeiras, sendo que a (2) não justifica a (1).

Teoria da Computação

Qual é a linguagem gerada pela gramática S → aSb, S → A, A → aA? a bm m a bm n ∅ a bn m a bj i

Exercicio 3

Respostas

Crie sua conta grátis para liberar essa resposta. 🤩

Ainda com dúvidas?

Essa pergunta também está no material:

Exercicio 3

A diferença entre autômatos finitos e autômatos de pilha está na:
Pilha.
Controle finito.
Direção do movimento da cabeça de leitura.
Fita de entrada.
Cabeça de leitura.

Pilhas possuem somente uma entrada chamada de topo e são compostas por duas operações fundamentais. Sobre os conceitos de pilha, como é implementado os mecanismos de inserção/remoção?
FIFO.
FIFA.
LIFO.
FFLL.
PEPS.

Gramáticas definem linguagens, sendo especificações finitas de regras de geração de cadeias. Nesse sentido,
assinale a alternativa incorreta.
a + b denota {a} U {b} = {a, b}
V U T = Σ
λ ∈ Σ*
V ∩ T = ∅
V ∩ T = Σ*

Uma linguagem L gerada a partir de uma dada GLC onde não existem ciclos no grafo direcionado gerado a partir das regras de produção dessa GLC, é denominada de:
Finita.
Recursiva.
Infinita.
Irrestrita (sem restrições).
Sem contexto.

Mais conteúdos dessa disciplina

Teoria da Computação

Qual é a linguagem gerada pela gramática S → aSb, S → A, A → aA? a bm m a bm n ∅ a bn m a bj i

Exercicio 3

Respostas

Crie sua conta grátis para liberar essa resposta. 🤩

Ainda com dúvidas?

Essa pergunta também está no material:

Exercicio 3

A diferença entre autômatos finitos e autômatos de pilha está na:Pilha.Controle finito.Direção do movimento da cabeça de leitura.Fita de entrada.Cabeça de leitura.

Pilhas possuem somente uma entrada chamada de topo e são compostas por duas operações fundamentais. Sobre os conceitos de pilha, como é implementado os mecanismos de inserção/remoção?FIFO.FIFA.LIFO.FFLL.PEPS.

Gramáticas definem linguagens, sendo especificações finitas de regras de geração de cadeias. Nesse sentido,assinale a alternativa incorreta.a + b denota {a} U {b} = {a, b}V U T = Σλ ∈ Σ*V ∩ T = ∅V ∩ T = Σ*

Uma linguagem L gerada a partir de uma dada GLC onde não existem ciclos no grafo direcionado gerado a partir das regras de produção dessa GLC, é denominada de:Finita.Recursiva.Infinita.Irrestrita (sem restrições).Sem contexto.

Mais conteúdos dessa disciplina

A diferença entre autômatos finitos e autômatos de pilha está na:
Pilha.
Controle finito.
Direção do movimento da cabeça de leitura.
Fita de entrada.
Cabeça de leitura.

Pilhas possuem somente uma entrada chamada de topo e são compostas por duas operações fundamentais. Sobre os conceitos de pilha, como é implementado os mecanismos de inserção/remoção?
FIFO.
FIFA.
LIFO.
FFLL.
PEPS.

Gramáticas definem linguagens, sendo especificações finitas de regras de geração de cadeias. Nesse sentido,
assinale a alternativa incorreta.
a + b denota {a} U {b} = {a, b}
V U T = Σ
λ ∈ Σ*
V ∩ T = ∅
V ∩ T = Σ*

Uma linguagem L gerada a partir de uma dada GLC onde não existem ciclos no grafo direcionado gerado a partir das regras de produção dessa GLC, é denominada de:
Finita.
Recursiva.
Infinita.
Irrestrita (sem restrições).
Sem contexto.