retagged by
1,785 views
3 votes
3 votes

#8 Determine whether or not the following languages are context-free

(a) L= { anwwRan : n>=0 , w ∈ {a,b}* }

(b) L = { anbjanbj : n>=0, j>=0 }

(c) L = { anbjajbn : n>=0, j>=0 }

(d) L= { anbjakbl : n+j<=k+l }

(e) L = { anbjakbl : n<=k, j<=l }

(f) L = { anbncj : n<=j }

(g) L = { w ∈ {a,b,c}* : na(w)=nb(w)=2nc(w) }

My answers are :

(a)CFL

(b)Not CFL

(c)CFL

(d) CFL

(e)Not CFL

(f)Not CFL

(g) Not CFL

Please verify.

retagged by

2 Answers

4 votes
4 votes

a) CFL (More specifically Non-Deterministic CFL)

b) NOT CFL (Read the reason in Comment


c) CFL (Deterministic CFL)

d) CFL (Deterministic CFL)

e) CFL (Deterministic CFL) { if you look closely then you will see that its same problem as (d) }

f) It's not CFL, because there is two conditions,  $ \{ ( |a| == |b| ) and  ( |a| \& |b| <= |c| ) \}  $

g) Its not CFL. 

edited by
2 votes
2 votes

(a) L= { anwwRan : n>=0 , w ∈ {a,b}* }  is CFL.

(b) L = { anbjanbj : n>=0, j>=0 } is CSL since alternate comparision.

(c) L = { anbjajbn : n>=0, j>=0 } is CFL .Done by single stack.

(d) L= { anbjakbl : n+j<=k+l } is CFL .

(e) L = { anbjakbl : n<=k, j<=l } is CFL since same as (d) but represenation is diffrent. 

(f) L = { anbncj : n<=j } is CSL since Need atleast two stack.

(g) L = { w ∈ {a,b,c}* : na(w)=nb(w)=2nc(w) } is well known CSL. 

edited by

Related questions