The Gateway to Computer Science Excellence
0 votes
38 views
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 by Boss (15.4k points) | 38 views
0
Not deterministic
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
+1
@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.
0

@Shubham Shukla 6 okay got it

 

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,258 answers
198,086 comments
104,735 users