0 votes 0 votes Give reasons why one might conjecture that the following language is not deterministic. $L =$ { $a^nb^mc^k : n = m$ or $m = k$}. Theory of Computation peter-linz peter-linz-edition4 theory-of-computation context-free-language + – Naveen Kumar 3 asked Jun 23, 2019 Naveen Kumar 3 627 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply shivanisrivarshini commented Jun 23, 2019 i edited by shivanisrivarshini Jun 24, 2019 reply Follow Share Not deterministic 0 votes 0 votes Ravijha commented Jun 24, 2019 reply Follow Share I think it can also be written as L={a^n b^n c^n} and then it is CSL it can solved by Linear bounder automata 0 votes 0 votes Shubham Shukla 6 commented Jun 24, 2019 reply Follow Share @ravijha thats not correct you changed the question,now the strings in language accpeted going to be less if you say that way. As one can see there are two conditions which can make the language accepted by pda. So in first condition we would be pushing a and popping b to check equivalence for n=m and just do nothing when you see c , similarly for second condition we goona skip a and push b and pop c to check equivalence of number of b'c and c's. So this way its gonna make it non deterministic. 2 votes 2 votes Ravijha commented Jun 24, 2019 reply Follow Share @Shubham Shukla 6 okay got it 0 votes 0 votes Please log in or register to add a comment.
