Test by Bikram | Theory of Computation | Test 1 | Question: 17

Question

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

• A. DCFL
• B. CFL but not DCFL
• C. Non-CFL
• D. Regular Language

Comments

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.

Answer 1

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

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

Answer 2

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