The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

$\overline{L(M)}$ is

  1. Regular 
  2. DCFL but not regular
  3. CFL but not DCFL
  4. Recursive but not CFL
asked in Theory of Computation by Boss (34.5k points)
edited by | 63 views
CFL is not closed under complementation .so option 4 is most suitable .what is the answer?
answer is B but i'm not able to understand PDA itself where is the stack symbol?
state 1 says seeing a if the top of the stack epsilon then push a i guess
I think this language is a^nb^n then it should not be DCFL

1 Answer

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.


answered by Boss (11.9k points)
edited by
didn't you get ambiguous when seeing an a, either it is push or skip?

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

is it correct statement? 

@shaikh yes i didnt noticed that ($,ε,ε) which says if stack empty goto state q4... and if stack was empty why we need to pop a again... at q4 isnt that a null statement.
@srestha mam :here it means δ(q1,b,a)={(q1,ϵ)} means pop each a on seeing a b. or for every b pop each a. there is one pop for q0 to q1 and than it will continue for q1.

stack pushing only 1 a in

Not aa that we pushing

then for every b how an a will poped?

Related questions

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
49,532 questions
54,126 answers
71,046 users