retagged by
786 views
2 votes
2 votes
L ={$a^nb^k$ | n$\leq$k$\leq$2n} CFL or not??

L ={$a^ib^jc^k$ | (i$\leq$j) or (j$\leq$i), j=k} CFL or not??
retagged by

2 Answers

Best answer
5 votes
5 votes

Both are CFL

1) L = anbk ( n<=k<=2n)

for this language we can write the grammar as follows

S -> aSb | aSbb | $\epsilon$

2) L ={aibjck | (i≤j) or (j≤i), j=k}

i<=j or j<=i  simply means i and j can be anything

So only one condition remains i.e. j=k  ( number of b and c equal )

Hence it is CFL

selected by
0 votes
0 votes
2nd one is not CFL.. It needs to statisfy 2 conditions ( (i≤j) or (j≤i) )  and j=k .

Related questions

3 votes
3 votes
2 answers
1
1 votes
1 votes
1 answer
2
jugnu1337 asked Apr 16, 2023
348 views
$a^{p}b^{p}a^{p} where p>=0$ can i write this lang. as cfl when a come push in to the stack when b skip all b’s again when a pop all the a from the stack …..
2 votes
2 votes
1 answer
3
Souvik33 asked Nov 23, 2022
302 views
If L and $L^{c}$ both are CFL, the L must be DCFL a. TRUE b.FALSE
1 votes
1 votes
2 answers
4
atulcse asked Jan 21, 2022
676 views
Is the following language a DCFL? Please explain your reasoning.