1 votes 1 votes Is the language $L =$ {$a^nb^n : n ≥ 1$} $∪$ {$b$} deterministic? Theory of Computation peter-linz peter-linz-edition4 theory-of-computation context-free-language + – Naveen Kumar 3 asked Jun 23, 2019 Naveen Kumar 3 282 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply akshay7797 commented Sep 23, 2019 reply Follow Share yes 0 votes 0 votes Doraemon commented Sep 23, 2019 reply Follow Share @akshay7797 how is this regular please explain. I think this is an NCFL. 0 votes 0 votes akshay7797 commented Sep 23, 2019 reply Follow Share 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 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes $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. Naveen Kumar 3 answered Sep 23, 2019 Naveen Kumar 3 comment Share Follow See all 0 reply Please log in or register to add a comment.