Register

TOC

• retagged by
1,572 views
5 votes
5 votes

• retagged by
User Avatar

1 Answer

2 votes
2 votes
only L2 n L4 are CFL n also DPDA can be constructed for both as in L2 comparison between I and j doesn't matter bcz of "OR" is betn.

N in L4 we only need to compare i and j n we will need two states for k as even to be accepted.

L1 n L3 require 2 comparisons so not possible by PDA.....

correct if wrong...
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

3 votes
3 votes
2 answers
1
Jiten008 asked Oct 24, 2023
367 views
TOC - Self Doubt
Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?
Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?
User Avatar
2 votes
2 votes
1 answer
2
rahuljai asked Dec 13, 2018
1,085 views
TOC Which is(are) regular? Please explain 1 and 4.
Which of the following languages is regular? L = { bba (ba)* a^n-1 | n> 0 } L = {a^nb^n | n < 1000 } L = {a^nb^k | n is odd or k is even } L = {wxw^R | w,x ∈(0+1)* } 1, 3 and 4 2, 3, 4 2, 3 1, 2, 3, 4
Which of the following languages is regular? L = { bba (ba)* a^n-1 | n 0 }L = {a^nb^n | n < 1000 }L = {a^nb^k | n is odd or k is even }L = {wxw^R | w,x ∈(0+1)* }1, 3 a...
User Avatar
2 votes
2 votes
0 answers
3
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
0 votes
0 votes
1 answer
4
UltraRadiantX asked Oct 9, 2021
472 views
Closure Properties of Languages
let L = “CFL but not REGULAR”, Can we get complement of L as CFL? Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, its complement can never be RE.
let L = “CFL but not REGULAR”, Can we get complement of L as CFL?Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, it...
User Avatar
Link Copied!