Register

Regular and CFL

792 views
1 votes
1 votes

  1.   LC may be CFL
  2.   LC cannot be CFL
  3.   LC may be regular
  4.   LC may or may not be CFL
User Avatar

2 Answers

1 votes
1 votes
all options are correct except b) Lc cannot be CFL

All the closure properties are 1-way.

CFLs are not closed in intersection, it means that the intersection is not always a CFL, i.e., it may or may not be CFL.
User Avatar
0 votes
0 votes
Option 1 is wrong

CFL is not closed under intersection complementation and subtraction.

So Lc can be regular
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

758
views
1 answers
5 votes
Parshu gate asked Nov 16, 2017
758 views
Regular and CFL
Let L={ai bj ck ┤|if j is odd then i=k} where i,j,k>0. Which of the following option is true about L? L is CSL but not CFL L is CFL but not DCFL L is regular L is DCFL but not regular
User Avatar
3.0k
views
2 answers
10 votes
Mahesha999 asked Dec 25, 2016
3,010 views
Which of these languages are regular, CFL and CSL?
Consider the following statements:$L_1=\left\{\text{wxw$^R$|w$\in$(a,b)$^*$, x$\in$c }\right\}$L_2=\left\{\text{wy|w, y $\in$ (a, ... is context sensitive languages$L_1, L_4$ are context free, $L_2$ and $L_3$ is context sensitive languages
User Avatar
736
views
1 answers
2 votes
Tuhin Dutta asked Dec 4, 2017
736 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?
User Avatar
304
views
0 answers
2 votes
h4kr asked Dec 23, 2022
304 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 ... ? Please tell how would check for the grammer of this language even if it is in CSL.Thank you
User Avatar
Link Copied!