TIFR CSE 2017 | Part B | Question: 4

Question

Let $L$ be the language over the alphabet $\{1, 2, 3, (, )\}$ generated by the following grammar (with start symbol $S$, and non-terminals $\{A, B, C\}$):

$ S \rightarrow A \: B \: C \\ A \rightarrow ( \\ B \rightarrow 1 \: B \mid 2 \: B \mid 3 \: B \\ B \rightarrow 1 \mid 2 \mid 3 \\ C \rightarrow )$

Then, which of the following is TRUE?

• A. $L$ is finite
• B. $L$ is not recursively enumerable
• C. $L$ is regular
• D. $L$ contains only strings of even length
• E. $L$ is context-free but not regular

Comments

nice comment by Manu sir

https://gateoverflow.in/628/gate2000-1-5?show=165762#c165762

---

The grammar looks like a concatenation of three regular grammars, one which produces only (, one which produces only ), and one which produces combinations of 1, 2, 3. This can be observed from the first rule $S → ABC$. So it has to be regular..

---

This question wasn’t properly rendered in the GO PDF. Looks good here.

Answer 1

Language accepted by that grammar is:
$( (1+2+3)^+)$
Hence, regular!

Correct Answer: $C$

Comments

NO  , ITS CORRECT  THERE SHOULD BE +

---

but for regular language, The productions must be in the form X → a or X → aY.

where X, Y ∈ N (Non terminal)

and a ∈ T (Terminal)

then how should interpret such type of question? plz explain.

---

Non-regular grammars may produce regular languages.

Imo the final grammar given above can be visualized as a grammar representing three separate regular languages concatenated together (each language given by regular grammars where A, B, C are their start symbols). Regular languages are closed under concatenation.

Answer 2

In the question above they are asking about the language accepted by the grammar not about the grammar,

we can rewrite the grammar as,

S -> ( B )

B-> 1B | 2B | 3B

B-> 1 | 2 | 3

you can generate any combination of 1,2,3 by the above grammar prefixed by '(' and suffixed by ')'. For this language, Finite automata can also be constructed.

let q0 be the initial state and q3 be the final state with transition function below->

(->q0, '(' ) = q1

(q1, 1) = q2

(q1, 2) = q2

(q1, 3) = q2

(q2, 1) = q2

(q2, 2) = q2

(q2, 3) = q2

(q2, ')' ) = q3*

The language for which Finite automata can be constructed is regular. Hence, the language generated by this grammar is regular.

Comments

I have a doubt. How this FA accept (12)? Can it move to final state in this case

---

@Manoja Rajalakshmi A Yes it will accept (12) by moving to final state on symbol ')" Draw DFA then you will get the solution.

Also, From regular expression ( (1+2+3)⁺)  you can generate string '(12)'.

---

Ok thank you. I thought on '2' it will move to q1. Doubt cleared.