GATE IT 2007 | Question: 49

Question

Consider the following grammars. Names representing terminals have been specified in capital letters.
$$\begin{array}{|llll|}\hline G1 :  &  \text{stmnt} & \rightarrow & \text{WHILE (expr) stmnt} \\%\hline 
\text{}  &  \text{stmnt} & \rightarrow & \text{OTHER} \\%\hline 
\text{}  &  \text{expr} & \rightarrow & \text{ID} \\\hline 
G2 :  &  \text{stmnt} & \rightarrow & \text{WHILE (expr) stmnt} \\%\hline
\text{}  &  \text{stmnt} & \rightarrow & \text{OTHER} \\%\hline
\text{}  &  \text{expr} & \rightarrow & \text{expr} + \text{expr} \\%\hline
\text{}  &  \text{expr} & \rightarrow & \text{expr} * \text{expr} \\%\hline
\text{}  &  \text{expr} & \rightarrow & \text{ID} \\\hline  \end{array}$$

Which one of the following statements is true?

• A. $G_1$ is context-free but not regular and $G_2$ is regular
• B. $G_2$ is context-free but not regular and $G_1$ is regular
• C. Both $G_1$ and $G_2$ are regular
• D. Both $G_1$ and $G_2$ are context-free but neither of them is regular

Comments

i am getting both as regular

is it correct?

---

What approach you used?

---

G1 can be written as

A->aBA

A->c

B->b

G2 as

A->aBA

A->c

B->B+B

B->B*B

B->b

RE for G1 would be (ab)⁺c

RE for G2 would be (ab(*b U +b)^*)⁺c

For both DFA is possible. 

Is this correct approach!

---

Yes. You are correct- except that you didnt consider ( and ) as terminals, but answer is correct. You don't need to try and get a regular expression (no problem in doing also). Trying to get a regular grammar is sometimes easier. I have added that here.

---

Given grammars can be re-written as:
Say, while = w, expr =E, stmt = S, other = o ID=  i
Here, we can write a right linear grammar for G₁ as
S -> w(E)S
S -> o
E->i

So, L(G₁) is regular.
Now for G₂ also we can write a right linear grammar:
S -> w(E)S

S -> o

E -> E+E
E -> E*E
E->i
So, L(G₂) is regular

so why not option  c both  are regular ; why they are not regular kindly explain

---

Is G2  left recursive?

---

For being Regular Grammar at most 1 non-terminal on the right side of any production.

S->Aa  or S->aA

---

I also thought the same thing… is this reasoning correct tho?

---

I think some people get pleasure down voting things. If someone gets wrong answer have some patience to know how the guy reached there.
Glad the down voting is now restricted.

---

@Sandeep Verma

Because they are asking about Grammar , not about language of Grammar.

Answer 1

Regular grammar is either right linear or left linear. A left linear grammar is one in which there is at most $1$ non-terminal on the right side of any production, and it appears at the left most position. Similarly, in right linear grammar non-terminal appears at the right most position.

Here, we can write a right linear grammar for $G1$ as

$S \rightarrow w(E$
$E \rightarrow id)S$
$S \rightarrow o$

(w - WHILE, o - OTHER)

So, $L(G1)$ is regular.

Now for $G2$ also we can write a right linear grammar:

$S \rightarrow w(E$
$E \rightarrow id)S$
$E \rightarrow id+E$
$E \rightarrow id*E$
$S \rightarrow o$

making its language regular. 

So, both $G1$ and $G2$ have an equivalent regular grammar. But given in the question both these grammars are neither right linear nor left linear and hence not a regular grammar. So, D must be the answer. 

http://www.cs.odu.edu/~toida/nerzic/390teched/regular/grammar/reg-grammar.html

Comments

The more simple answer can be, both grammar does not follow the rules of regular grammar.

---

@Arjun Sir G1 is regular 

S → w(E)S
S → o
E → i

is right-linear

1. S → w(E)S

   w ( E ) are terminals (since E → i eventually produces a terminal)There is exactly one nonterminal, S, and it appears at the right end

2. S → o,Only terminals on the right-hand side

3. E → i , Only terminals on the right-hand side

So all productions satisfy the right-linear form

---

No, it is wrong E is a non terminal you cant replace E with terminal while checking RL or LL

Answer 2

http://stackoverflow.com/questions/13816439/left-linear-and-right-linear-grammars

refer this to learn the left and right grammars

Comments

what kind of answer is this where not even the right option is mentioned!! and then it got 2 upvotes too !  😶

---

Open the page @adarsh u will know it

---

i already know the answer @prajjwalsingh_11 , however in this "answer" post , the reference is an explanation, so for clarity , selected option should be mentioned here.

---

They are social media leeches just like 4 mor#ns upvoted a mor#n

Answer 3

G1: 

stmnt -> WHILE (ID) stmnt

stmnt-> OTHER   

[S-> AS/B 

B-> b ]
Language: L(G1) = (WHILE(ID))* OTHER
Regular expression: (A)*B .
Thus G1 is regular.

G2:
- Because of productions expr → expr + expr 

and expr → expr * expr (non-linear), 

G2 is context-free but not regular.

Answer: B