in Theory of Computation edited by
215 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
in Theory of Computation edited by
by
215 views

1 comment

a^nb^n and a^mb^2m both are in DCFL

DCFL is not closed under union. So option A and option D is discarded.

Now grammar of the given language is
S->S1 | S2     
S1->aS1b | ab
S2-> aS2bb | abb

which is CFG. So option C is discarded.

OPTION B is right answer.

0
0

2 Answers

4 votes
4 votes
Best answer
(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