GATE IT 2007 | Question: 46

Question

The two grammars given below generate a language over the alphabet $\{x, y, z\}$

• $G1 :  S \rightarrow  x \mid z \mid x \ S \mid z \ S \mid y \ B$
  $\qquad B  \rightarrow y \mid z \mid y \ B \mid z \ B$
• $G2 :  S \rightarrow y \mid z \mid y \ S \mid z \ S \mid x \ B$
  $\qquad B \rightarrow y \mid  y \ S $

Which one of the following choices describes the properties satisfied by the strings in these languages?

• A. $G1$ : No $y$ appears before any $x$
  $G2$ : Every $x$ is followed by at least one $y$
• B. $G1$ : No $y$ appears before any $x$
  $G2$ : No $x$ appears before any $y$
• C. $G1$ : No $y$ appears after any $x$
  $G2$ : Every $x$ is followed by at least one $y$
• D. $G1$ : No $y$ appears after any $x$
  $G2$ : Every $y$ is followed by at least one $x$

Comments

Meta Note: This question is incorrectly tagged as CFL.

---

Regular expression for 

Every y is followed by at least one x :-   (x+z+yx)⁺  

No x appears before any y  :-   (y+z)⁺ + (y+z)* x (x+z)⁺ 

No y appears after any x  :-      (x+z)⁺ + (y+z)* y (x+z)⁺ 

Correct me if i am wrong .....

---

 

S->xS

xyB

xyy

y can come after x

Option C eliminated

---

SO, the trick here is don't draw the dfa/nfa, don't write any expression.

Just observe the question, 

First we need to choose before or after in G1 

G1 : S → x ∣ z ∣ xS ∣ zS      (from this we can see that y dosen't come first)

Hence, No y appears before any x,   Opt. C and D eliminated.

G2 : xB    and  B → y ∣ yS    (from this we can say that after every x, atleast one y comes)

other expressions were just to create confusion and waste time

Hence, Ans is (A)

Answer 1

From Above grammar:

Regular expression for $G1: (x+z)^+ + (x+z)^*y(y+z)^+ $

Regular expression for $G2 :(y+z+xy)^+$

Option A is correct .

Comments

Or

$G_{1} = (X+Y)^{*}(X+Z+Y(Y+Z)^{+}) $

---

@Praveen Saini @Sachin Mittal 1 sir why you made one extra state for the final state, it can be S,B both as a final state in DFA constructed by @Sachin Mittal 1?

---

@air1ankit..
If S is final state, then machine will accept some extra strings like epsilon...(by extra strings, i mean the strings that are not generated by given grammar)
Similarly if B is final state, then  machine accepts some extra strings like xy which are not in language.
Hence they are not taken as final..
Hope this clears :)

Answer 2

G1: $\\(x+z)^*(x+z)+(x+z)^*y(y+z)^*(y+z)$

  $=(x+z)^++(x+z)^*y(y+z)^+$

G2: $\\(y+z+xy)^*xy+(y+z+xy)^*(y+z)$

  $=(y+z+xy)^*(xy+y+z)$

  $=(y+z+xy)^+$

after removing loop:

$Ans:A$

Answer 3

A)	G1 : No y appears before any x G2 : Every x is followed by at least one y

Comments

@Sachin Mittal 1

Hello Sir,

what's the approach of creating final state. As the nfa diagram you provided for the above grammar has F as final state not S and B.

Answer 4

For the above question we can see that for all options, properties satisfied by the strings could be defined as some relation between x and y alphabets.
For Grammar 1, Strings with a combination of both x and y can be generated with the following form of production(s) of the grammar only.

S–>xS –>xyB or

S–>zS–>zxS–>zxyB

(In case starting production is S–>x| z| yB, it cannot give both x and y in the string)
Hence in any string with x and y both no y can appear before x can be described as a property satisfied by the strings of the language.

Similarly for Grammar 2, Strings with a combination of both x and y can be generated with the following

form of production(s) of the grammar only.

Answer 5

Solving using parse tree method

 

(A) is the correct answer

Cross verify using the tree

Parse tree for G1

parse Tree for G2

Answer 6

The correct choice is A.

Here is a step-by-step analysis of both grammars.

 

Analysis of Grammar G1

 

• Rules:

  • $S \to x \mid z \mid xS \mid zS \mid yB$

  • $B \to y \mid z \mid yB \mid zB$

1. Analyze $B$: The rules $B \to (y \mid z) \mid (y \mid z)B$ show that $B$ generates any string consisting of one or more $y$'s and $z$'s. $B$ can never produce an $x$.

2. Analyze $S$: The rules $S \to (x \mid z) \mid (x \mid z)S$ show that a derivation from $S$ can produce any sequence of $x$'s and $z$'s (e.g., $x, z, xx, xz, \dots$).

3. The "Switch" Rule: The derivation from $S$ can switch to $S \to yB$.

   • Once this rule is used (e.g., $S \Rightarrow xS \Rightarrow xyB$), the non-terminal $S$ is gone.

   • The derivation must continue from $B$, which can only produce $y$'s and $z$'s.

   • This means that as soon as a $y$ is generated, no more $x$'s can ever be generated in that string.

4. Conclusion for G1: A string can consist of only $x$'s and $z$'s (e.g., $xxz$), or it can start with $x$'s and $z$'s, but once a $y$ appears, no more $x$'s can follow (e.g., $xzyyz$). Therefore, it is impossible to generate a string where a $y$ appears before an $x$.

   • This matches the property: "No $y$ appears before any $x$."

---

 

Analysis of Grammar G2

 

• Rules:

  • $S \to y \mid z \mid yS \mid zS \mid xB$

  • $B \to y \mid yS$

1. Analyze $S$: The rules $S \to (y \mid z) \mid (y \mid z)S$ show that $S$ can generate any sequence of $y$'s and $z$'s.

2. The "Switch" Rule: The derivation from $S$ can use the rule $S \to xB$.

   • This rule is the only way to introduce an $x$ into the string.

   • After $x$ is generated, the derivation must continue from $B$.

3. Analyze $B$: The rules for $B$ are $B \to y \mid yS$.

   • In both cases ($B \to y$ or $B \to yS$), the very next symbol to be generated must be a $y$.

4. Conclusion for G2: Since every $x$ is introduced by $S \to xB$, and $B$ must immediately produce a $y$, it is guaranteed that every $x$ in any generated string will be followed by at least one $y$.

   • This matches the property: "Every $x$ is followed by at least one $y$."

---

 

Final Decision

 

• G1: No $y$ appears before any $x$.

• G2: Every $x$ is followed by at least one $y$.

This corresponds exactly to Option A.