edited by
5,595 views
25 votes
25 votes

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?

  1. $G1$ : No $y$ appears before any $x$
    $G2$ : Every $x$ is followed by at least one $y$
  2. $G1$ : No $y$ appears before any $x$
    $G2$ : No $x$ appears before any $y$
  3. $G1$ : No $y$ appears after any $x$
    $G2$ : Every $x$ is followed by at least one $y$
  4. $G1$ : No $y$ appears after any $x$
    $G2$ : Every $y$ is followed by at least one $x$
edited by

5 Answers

Best answer
24 votes
24 votes

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 .

edited by
4 votes
4 votes

A)

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

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:

Related questions

67 votes
67 votes
3 answers
1
Ishrat Jahan asked Oct 30, 2014
12,633 views
Consider the following grammars. Names representing terminals have been specified in capital letters.$$\begin{array}{llll}\hline \text{$G1$ :} & \text{stmnt} & \text{$\...
42 votes
42 votes
7 answers
4
Ishrat Jahan asked Oct 30, 2014
7,776 views
Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$Which deterministic finite automaton accepts the language represented by the regular expression $R$?