Question

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

$G1:S\to x\mid z\mid xS\mid zS\mid yB$
$B\to y\mid z\mid yB\mid zB$

$G2:S\to y\mid z\mid yS\mid zS\mid xB$
$B\to y\mid yS$

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

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

Answer 1

The correct option is D G1: No y appears before any x


G2: Every x is followed by at least one y
$G1:S\to x\mid z\mid xS\mid zS\mid yB$
$B\to y\mid z\mid yB\mid zB$
$B\to (y+z{)}^{+}$

Substitute in S to get

$S\to x\mid z\mid xS\mid zS\mid y(y+z{)}^{+}$

Now solution of S is
$S\to (x+z{)}^{\ast }S$
$S\to (x+z{)}^{\ast }(x+z+y(y+z{)}^{+})$

So, L(G1) = S = $(x+z{)}^{+}+(x+z{)}^{\ast }y(y+z{)}^{+}$

G1 generates every string in which "no y appears before any x"

$G2:S\to y\mid z\mid yS\mid zS\mid xB$
$B\to y\mid yS$

Substitute B in S to get

$S\to y\mid z\mid yS\mid zS\mid xy\mid xyS$

Now solution of S is

$S\to (y+z+xy{)}^{\ast }S$
$S\to (y+z+xy{)}^{\ast }(y+z+xy)$
So L(G2) = S = (y + z +xy)${}^{+}$
G2 generates every string in which "every x followed by atleast one y"