Register

GO Classes DPP | GATE CS | Theory of Computation | DCFL

• edited by
58 views
1 1 vote

Let $A=\{a^n b^n\mid n\ge1\}$. Define $L_a=A\cup\{a\}$ and $L_b=A\cup\{b\}$. Which statements are correct?

  1. $L_a$ is a DCFL.
     
  2. $L_b$ is a DCFL.
     
  3. Both $L_a$ and $L_b$ are regular.
     
  4. Both $L_a$ and $L_b$ are not regular.
     
  5. This works because adding a finite regular language to a DCFL preserves DCFL.
     
  6. This works because DCFLs are closed under union with any DCFL.

1 Answer

1 1 vote

$A=\{a^n b^n\mid n\ge1\}$ is a standard DCFL. 

The singleton languages $\{a\}$ and $\{b\}$ are finite, so they are regular. 

Since DCFL $\cup$ regular is DCFL, both $L_a$ and $L_b$ are DCFLs.

They are still not regular. If $L_a$ were regular, then removing the finite regular language $\{a\}$ would make $A$ regular, which is false. 

Same logic works for $L_b$. 

So A, B, D, and E are correct. 

F is false because DCFLs are not closed under arbitrary union.

• edited by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

3 3 votes
1 1 answer
96
96 views
GO Classes asked Sep 17
96 views
GO Classes DPP | GATE CS | Theory of Computation | DCFL
Let $L=\{w\in\{a,b\}^*\mid n_a(w)\ne n_b(w)\}$. Which statements are correct?$L$ is regular. $L$ is DCFL. $L$ is not CFL. A DPDA can maintain the current surplus using th...
2 2 votes
1 1 answer
68
68 views
GO Classes asked Sep 17
68 views
GO Classes DPP | GATE CS | Theory of Computation | DCFL
Let $L_1=\{wcw^R\mid w\in\{a,b\}^*\}$ and $L_2=\{ww^R\mid w\in\{a,b\}^*\}$. Which statements are correct?$L_1$ is a DCFL. $L_2$ is a DCFL. $L_2$ is a CFL. $L_2$ is not ac...
2 2 votes
1 1 answer
76
76 views
GO Classes asked Sep 17
76 views
GO Classes DPP | GATE CS | Theory of Computation | CFL & DCFL
Let $L=\{a^i b^j c^k\mid i=j\text{ or }j=k,\ i,j,k\ge0\}$. Which statements are correct?$L$ is a CFL. $L$ is a DCFL. $L$ can be written as union of two CFLs: one checking...
1 1 vote
1 1 answer
57
57 views
GO Classes asked Sep 17
57 views
GO Classes DPP | GATE CS | Theory of Computation | Union of DCFL
Let $L_1=\{a^n b^n\mid n\ge0\}$, $L_2=\{a^n b^{2n}\mid n\ge0\}$, and $L=L_1\cup L_2$.Which statements are correct?$L_1$ is a DCFL. $L_2$ is a DCFL. $L$ is a CFL. $L$ is a...