Peter Linz Edition 4 Exercise 7.3 Question 3 (Page No. 200)

Question

Is the language $L =$ {$a^nb^n : n ≥ 1$} $∪$ {$b$} deterministic?

Comments

yes

---

@akshay7797    how is this regular please explain.

I think this is an NCFL.

 

---

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.

Answer 1

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