1,383 views
2 votes
2 votes
cfl are closed under

a) min b)max c)half d)alt e)none of these

cfl are not closed under

init

l/a

cycle

set diffeence

1 Answer

1 votes
1 votes
min(Not Closed) ex- {L = { $a^{i}b^{j}c^{k}$ | k= min(i,j), i,j,k>0 }}

max(Not Closed) ex- {L = { $a^{i}b^{j}c^{k}$ | k= max(i,j), i,j,k>0 }}

half(Not Closed)

ex- Let L = { $a^{n} b^{n} c^{i} dd^{3i}d$ | n>0, i>0 } Since CFL is closed under intersection with regular languages, we can do half(L) ∩ a*b*c*d which splits L into two halves: $a^{n} b^{n} c^{i} d$ and $ d^{3i}d$ In order for these to be of equal length, i = n, So half(L) ∩ a*b*c*d = $a^{n} b^{n} c^{n} d$, which we know is not a CFL.

alt(Not Closed)

ex - ( If w = a1a2....an and x = b1b2....bm and y= c1c2c3.......cl are strings of the same length, define alt(w,x,y) to be the string in which the symbols of w,x and y alternate, starting with w, that is a1b1c1a2b2c2....anbmcl).

init(closed)

cylcle(closed)

I/a (no idea what is this)

set difference(not closed)

Related questions

3 votes
3 votes
1 answer
1
iarnav asked Nov 1, 2017
556 views
If L1 = Regular L and L2 = CFL then L1 UNION L2?= L1 U L2= Reg L U CFL= CFL U CFL= CFL is it True?
0 votes
0 votes
1 answer
3
UltraRadiantX asked Oct 9, 2021
450 views
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...