edited by
386 views
2 votes
2 votes

The language $L =\{a^n \ b^n \mid  n \geq 1\} \cup \{a^m \ b^{2m} \mid m \geq 1\}$ is:

  1. DCFL
  2. CFL but not DCFL
  3. Non-CFL
  4. Regular Language
edited by

2 Answers

Best answer
4 votes
4 votes
(B) is correct answer, following is the Context Free Grammar:

S->S1 | S2     
S1->aS1b | ab
S2-> aS2bb | abb
selected by
0 votes
0 votes

We need non-determinism in PDA to accept this.

After pushing all the a's, create two instances where

  • The first instance pops one a for one b
  • The second instance  pops one a for two b's

Or create two instances from the start state where

  • The first instance pushes one a for one a and pops one a for one b
  • The second instance pushes two a's for one a and pops one a for one b.

Hence, Option B

Answer:

Related questions

6 votes
6 votes
2 answers
2
Bikram asked Nov 26, 2016
1,174 views
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is:DecidableUndecidable but semi-decida...
0 votes
0 votes
1 answer
3
Bikram asked Nov 26, 2016
294 views
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an:Decidable prob...
0 votes
0 votes
1 answer
4
Bikram asked Nov 26, 2016
201 views
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism