279 views
0 votes
0 votes
Is the language L = {a^nb^m
: n = m or n = m + 2} deterministic? Please anybody can clarify it.

1 Answer

2 votes
2 votes

It is not deterministic.

A deterministic language requires that its acceptors have a determined next state on every input. Here we have ${n = m}$ or ${n = m + 2}$. Let’s say we have a deterministic acceptor that accepts the language as specified. It pushes an ${a}$ into a stack and pops whenever ${b}$ is seen in the string. Consider what happens at the last stage. Either we’ll be left with an empty stack (${n = m}$) OR we will have ${0 }$ ${b}$’s left and ${2}$ ${a}$’s to pop (${n = m + 2}$). They both should be the accepting stages, since we claimed that our acceptor works for this language. Until the end is reached, the acceptor is unable to determine which accepting state to use for a particular input. This contradicts our assumption that the acceptor was deterministic. Consequently, the language itself is non-deterministic.

Related questions

1 votes
1 votes
1 answer
1
1 votes
1 votes
2 answers
2
ggwon asked Dec 29, 2022
727 views
L = {$a^{n+m}b^{n}a^{m} | n,m \geq 0$}Is the above language DCFL or CFL ?
2 votes
2 votes
2 answers
4