215 views

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

### 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.

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

S->S1 | S2
S1->aS1b | ab
S2-> aS2bb | abb

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

1 vote