Use the following grammar for all the questions below S ABCD B+b 7-1 a) Can you

Question

Use the following grammar for all the questions below S ABCD B+b 7-1 a) Can you derive the string bdd from this grammar? 7-1 b) Can you derive the string acc from this grammar? 7-1 c) Can you derive the string abcd from this grammar? 7-1 d) Can you derive the string aabbccdd from this grammar? 7-1 e) Can you derive the string aaaaaaabcdd from this grammar? 7-1 f) Can you derive the string abcddddddd from this grammar? 7-1 g) Give a regular expression that represents the language generated by this grammar 7-1 e) Is this a regular grammar? Why or why not?

Explanation / Answer

a) Yes

S -> ABCD
-> BCD
-> BCD
-> bCD
-> bD
-> bD
-> bdd

b) No, every string generated by this grammer will contain b & d because there is no rule similar to B -> or D ->

c) Yes

S -> ABCD
-> aABCD
-> aBCD
-> aBCD
-> abCD
-> abcCD
-> abcD
-> abcD
-> abcd

d) No, b can occur only once in the output string of this grammer since B -> b and B is not in RHS of any of the above rules except first rule.

e) Yes. To generate 7 a's use rule A -> aA 7 times then in the end substitue in place of A. Then replace B -> b. Then to one c use rule C -> cC then substitute in place of C. In the end replace D -> dd.

f) No, d can occur only twice in the output string of this grammer since D -> dd and D is not in RHS of any of the above rules except first rule.

g) (ap b cq dd ) where p, q >= 0

h) Yes it is a regular grammer. More specifically it is a right regular grammer.

If this helps please give a thumb up. Good Luck!!

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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