Considerando a gramática livre de contexto G = ({S, A, B}, {0, 1}, P, S)
P = {S -> A1B,
A -> 0A,
A -> 0,
B -> 0B,
B -> 1B,
B -> 1
B -> 0}
As palavras:
- 000111
- 11
- 1
São, RESPECTIVAMENTE:
a.
Aceita, rejeitada e rejeitada.
b.
Aceita, aceita e aceita.
c.
Rejeitada, rejeitada e rejeitada.
d.
Rejeitada, aceita e rejeitada.
e.
Aceita, rejeitada e aceita.
Soluções para a tarefa
Resposta:
a. Aceita, rejeitada e rejeitada
Explicação:
O ponto de partida é sempre o S, portanto A1B.
O A só dá origem a 0A e 0 e o B só da origem a 0B, 1B, 1 e 0.
Para determinar se as palavras seriam aceitas, realizamos a construção delas conforme a gramática fornecida pelo exercício e determinamos que as palavras serão, respectivamente, aceita, rejeitada e rejeitada. Deste modo, a alternativa A está correta.
Verificando se as palavras são aceitas pela gramática
A gramática informada pelo exercício apresenta os símbolos que podem construir as palavras. Vamos tentar construir as palavras de cada item para verificar se são aceitas ou rejeitadas.
- 000111
Temos A1B, podemos realizar a seguinte construção:
A1B -----A -> 0A,
0A1B -----A -> 0A,
00A1B ----A -> 0,
0001B ----B -> 1B,
00011B - B -> 1,
000111
A palavra 000111 é aceita.
- 11
A1B -----B -> 1,
A11 ----- ∉
Não existe uma regra em que A seja substituído por vazio, e os símbolos não podem permanecer ao final de uma palavra, logo ela será rejeitada.
- 1
A1B ----- ∉
Não existem regras em que A ou B sejam substituídos por vazio, e os símbolos não podem permanecer ao final de uma palavra, logo ela será rejeitada.
Então as palavras serão, respectivamente, aceita, rejeitada e rejeitada.
Deste modo, a alternativa A está correta.
Descubra mais sobre a Linguagem livre de contexto em: https://brainly.com.br/tarefa/25087373
#SPJ2