in Theory of Computation
571 views
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$}.
in Theory of Computation
571 views

4 Comments

edited by
Not deterministic
0
0
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
0
@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
2

@Shubham Shukla 6 okay got it

 

0
0

Please log in or register to answer this question.

Related questions