74 views

$\overline{L(M)}$ is

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

edited | 74 views
0
CFL is not closed under complementation .so option 4 is most suitable .what is the answer?
0
answer is B but i'm not able to understand PDA itself where is the stack symbol?
0
state 1 says seeing a if the top of the stack epsilon then push a i guess
0
I think this language is a^nb^n then it should not be DCFL

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.

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

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

is it correct statement?

0
@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.
0
@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.
0
0
@arvin

stack pushing only 1 a in

Not aa that we pushing

then for every b how an a will poped?