edited by
775 views
0 votes
0 votes

$\overline{L(M)}$ is

  1. Regular 
  2. DCFL but not regular
  3. CFL but not DCFL
  4. Recursive but not CFL
edited by

1 Answer

0 votes
0 votes

its a DCFL. how?

lets break it..

let the required states be q0,q1=non final states andq2,q4=final states(given that states with value 1 = non final , value=0 final state).

case 1:

we can goto final state without reading anything directly from qo to q4.

($,ε,ε) = means if stack empty we can goto final state. 

at state q0 :

(a,ε,a) means a can be pushed into the state qo without reading anything from the input. 

at state q4 : its a null statement as once stack is empty we will goto state q4 than how will we have a again..

(ε,a,ε) means pop a without reading anything from state q4.

conclusion for case 1 : it accepts ε.

case 2:

(b,a,ε) : for every b pop each a and soon as we have loop for state q1 .

($,ε,ε) means if stack empty goto state q3(final state).

conclusion : it can accept strings of anb : where n>=1

so we conclude that the given pda accepts ε , anb : where n>=0 (including ε also). = (DCFL)

so the required languauge is a DCFL overall. 

the question has asked for complement of L. which is also a dcfl.

 

edited by

Related questions

0 votes
0 votes
1 answer
1