Register

Complement CSL

• retagged by
1,730 views
3 votes
3 votes

Loading Question

• retagged by
User Avatar

1 Answer

3 votes
3 votes
l={w/w in (a+b+c+d)
a=b and b=cand  c=d and a=d and b=d and a=c}

which is csl and its complement will be cfl will be implemented by npda.

 

L1={ww /w in (a+b)*}

l1 language is csl  but its complement is cfl because in complement we have to mismatch the string which will be done easily by npda .

so should be (A) option ans.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

5 votes
5 votes
2 answers
1
Pradip Nichite asked Dec 31, 2015
4,837 views
Complement of CSL
Please some one explain. why complement of this language is CFL.
Please some one explain. why complement of this language is CFL.
User Avatar
2 votes
2 votes
0 answers
2
h4kr asked Dec 23, 2022
288 views
Is it CFL or CSL?
Is {$a^nb^nc^n$ | $n>=0$} CSL? After comparing both a and b, stack would be empty. So it can’t be CFL. So it is CSL or recursive. And does this language require more than 1 stack? Please tell how would check for the grammer of this language even if it is in CSL. Thank you
Is {$a^nb^nc^n$ | $n>=0$} CSL? After comparing both a and b, stack would be empty. So it can’t be CFL. So it is CSL or recursive. And does this language require more th...
User Avatar
2 votes
2 votes
1 answer
3
Tuhin Dutta asked Dec 4, 2017
708 views
Doubt in CSL and CFL
$a) \{\ 0^i\ 1^j\ 2^k\ \ | where\ i\ \neq j\ or\ j\ \neq k\ \}$ $b) \{\ 0^i\ 1^j\ 2^k\ \ | where\ i\ \neq j\ and\ j\ \neq k\ \}$ a) CFL(union of two OR-ed comparisons ) b) CSL( Double comaprison ) Am I correct?
$a) \{\ 0^i\ 1^j\ 2^k\ \ | where\ i\ \neq j\ or\ j\ \neq k\ \}$$b) \{\ 0^i\ 1^j\ 2^k\ \ | where\ i\ \neq j\ and\ j\ \neq k\ \}$a) CFL(union of two OR-ed compa...
User Avatar
Link Copied!