Consider the following grammar: rightarrow a b rightarrow b | b rightarrow a | a

Question

Consider the following grammar: rightarrow a b rightarrow b | b rightarrow a | a Which of the following sentences are in the language generated by this grammar? Put YES or NO in blank. baab _____ bbbab _____ bbaaaaa _____ bbab Consider the following grammar: rightarrow a c | | b rightarrow c | c rightarrow d | Which of the following sentences are in the language generated by this grammar? Put YES or NO in blank. abcd _____ acccbd _____ acccbcc _____ acd _____ accc Convert the following EBNF to BNF S rightarrow A {bA} A rightarrow a [b] A

Explanation / Answer

Question 1

a.baab = Yes

S->AaBb

->baBb

->baab

2.bbab = Yes

S->AaBb

->AbBb

->AbbBb

->bbbBb

->bbbab

3.bbaaaaa = No

S->AaBb

->AbaBb

->bbaBb

It not possible as every language has to end with b

4.bbab = Yes

S->AaBb

->AbBb

->bbBb

->bbab

Question 2

1.abcd = Yes

S->aScB

->abcB

->abcd

2.acccbd = NO

S->aScB

->acAcB

->acccB

Itis not possible to reach the labguage

3.acccbcc = No

S->aScB

->a<A>cB

->acAcB

->acccB

Itis not possible to reach the labguage

4.acd = No

S->aScB

->aAcB

->ac

It is not possible to reach the labguage

5.accc = Yes

s->aScB

->aAcB

->accB

->accA

->accc

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.