retagged by
2,570 views
1 votes
1 votes

The regular grammar for the language L= { $w\mid n_{a}$(w) and $n_{b} (w)$ are both even, $w \in \left\{a, b\right\}$ * } is given by : (Assume, $p, q, r$ and $s$ are states) 

  1. $p \rightarrow aq \mid br \mid \lambda, q \rightarrow bs \mid ap r \rightarrow as \mid bp, s \rightarrow ar \mid bq$, $p$ and $s$ are initial and final states. 
  2. $p \rightarrow aq \mid br , q \rightarrow bs \mid ap r \rightarrow as \mid bp, s \rightarrow ar \mid bq$, $p$ and $s$ are initial and final states. 
  3. $p \rightarrow aq \mid br \mid \lambda , q \rightarrow bs \mid ap r \rightarrow as \mid bp, s \rightarrow ar \mid bq$ $p$ is both initial and final states.
  4. $p \rightarrow aq \mid br , q \rightarrow bs \mid ap r \rightarrow as \mid bp, s \rightarrow ar \mid bq$ $p$ is both initial and final states. 
retagged by

1 Answer

Best answer
5 votes
5 votes

This is Even-Even Language. 

No of a's are divisible by 2 and No of b's are divisible by 2.

Design DFA for the language

Convert DFA to CFG 

Option C is correct.

You may refer: https://gateoverflow.in/2280/gate1997_20 for designing DFA

selected by
Answer:

Related questions

1 votes
1 votes
1 answer
1
makhdoom ghaya asked Jun 8, 2016
1,693 views
The context free grammar for the language $L= \left\{a^{n}b^{m}c^{k} \mid k = \mid n - m\mid , n \geq 0, m \geq 0, k \geq 0\right\}$ is $S \rightarrow S_{1}S_{3}, S_{1} \...
0 votes
0 votes
2 answers
2
makhdoom ghaya asked Jul 1, 2016
3,369 views
Match the following $:$$\begin{array} {cIcI} & \textbf{List – I} && \textbf{List – II} \\ \text{a.} & \text{DDL} & \text{i.} & \text{LOCK TABLE} \\ \text{b.} & \tex...
2 votes
2 votes
3 answers
3
makhdoom ghaya asked Jul 1, 2016
19,964 views
Let $R =\{A, B, C, D, E, F\}$ be a relation schema with the following dependencies $C \rightarrow F$, $E \rightarrow A$, $EC \rightarrow D$, $A \rightarrow B$. Which of t...
3 votes
3 votes
3 answers
4
makhdoom ghaya asked Jul 1, 2016
4,126 views
A clustering index is created when _______. Primary key is declared and ordered No key orderedForeign key orderedThere is no key and no order