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$
          $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$
          $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 .....

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.