5. Given the grammar G with productions S AS | b, A SA | b (a) Produce all strin

Question

5. Given the grammar G with productions S AS | b, A SA | b

(a) Produce all strings in L(G) of length less than or equal to 3.
(b) Show that this grammar is ambiguous.
(c) Is this grammar LL(1)? Explain.
(d) Is this language regular? Explain.

Bonus.1 Let QA denote a new class of abstract machines that act just like PDAs, except that the stack is replaced with a queue. Argue informally that QAs are at least as powerful as PDAs, in the sense that any language accepted by a PDA is also accepted by some QA. Hint: show that you can simulate a stack by using a queue.
Bonus2. Are QAs more powerful than PDAs, in the sense that there is a non-context-free language L that is accepted by some QA?

Explanation / Answer

a.
Grammar G: S => AS | b
A => SA | b
Hence all th strings in the grammar with length less than or equal to 3 are:
1. b
produced as: S => b
2. bb
produced as S => AS
=> bb
3. bbb
produced as S => AS
=> SAS
=> bbb

b. This grammar is ambiguous becasue a string in this grammar can be arrived at from more than 1 way or has more than 1 derivation tree.
For example, let us consider string bbb
First way to arrive at bbb:
S => AS
=> SA S
=> bbb
Second way to arrive at bbb:
S => AS
=>A AS
=>bbb

Therefore this grammar is ambiguous.

c:
This grammar does not belong to LL(1). Since the grammar is ambiguous (proved above), it also implies that it is not LL(1), since it has string which have more than 1 derivation.

d:
This grammar is regular. This is becasue of the following:
We can see that all the string that can be accepted by this grammar are: b, bb, bbb, bbbb, .....
Since the string set is not finiti it does not mean the grammar is not regular.
We can write a regular expression for the strings in this grammar as G = b* or bn where n>=1.
Therefore the language is regular becasue we can write regular expression for it which inturn implies that we can design the finite automata to accept the strings generated by the language. Hence it is a regular language.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

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