in Theory of Computation
184 views
1 vote
1 vote
Is the language $L =$ {$a^nb^n : n ≥ 1$} $∪$ {$b$} deterministic?
in Theory of Computation
184 views

3 Comments

yes
0
0

@akshay7797    how is this regular please explain.

I think this is an NCFL.

 

0
0
The question is about whether it is deterministic or not. It is not regular, but it is deterministic CFL because we can construct a PDA for it. In the PDA, push all a's onto the stack and then pop an a for each b. When top of the stack becomes empty, accept a single b and reach the final state.
0
0

1 Answer

1 vote
1 vote
$L_1$=$\{a^nb^n:n\ge 1\}$ is DCFL

$L_2$=$\{b\}$ is Regular

&, DCFL $\cup$ Regular = DCFL.

thus, $L=\{a^nb^n:n \ge 1\} \cup \{b\}$ is DCFL.

Hence, deterministic.

Related questions