Register

are following langauges CFL

1,371 views
2 2 votes
How to check whether following language are  context free

1)L= {a^nb^m ; n<=m<=3n}

2)L={w:2na(w) <=nb(w)<=3na(w)

 

making NPDA or DPDA  is not easy/convenient perhaps

2 Answers

0 0 votes
Both are not context free languages.

1)L= {a^nb^m ; n<=m<=3n}

In this language m depends on n. m and n are related to each other with two conditions i.e. m>=n and m<=3n so m can take any value between n and 3n. Here we have two conditions on m which cant be solved by using PDA or NPDA .

2)L={w:2na(w) <=nb(w)<=3na(w)

In this language  the number of  b's in  the strings  depends on the number of a's  i.e. 2na(w) <=nb(w)<=3na(w)

which again cant be solved by PDA or NPDA.
Voting & Accepting an answer helps improve the community
← Previous · ComplexityNext → · OS - Virtual Memory ...
← Previous in category · Theory of computatio...Next in category → · Following language: ...
Position:
Show:

Related questions

3 3 votes
1 1 answer
700
700 views
yes asked Dec 3, 2015
700 views
find which of the following CFL which are not, plz discuss one by one..
1. L={ai bj ck | k=max{i,j}}2. L={0n 1m | m&le;n2}3. L={0n 1m | m&ne;n2}4. {0n 1m |m&ne;n, m&ne;2n, m&ne;3n}5. {ai bj ck| i&ne;j or j&ne;k or i&ne;k}6. {0,1}*-{(0n 1)n | ...
5 5 votes
2 answers 2 answers
3.1k
3.1k views
gatecse asked Sep 12, 2014
3,053 views
Which of the following languages are CFL?
Which of the following languages are CFL?$$L_1= \left \{ 0^n 1^m \mid n \leq m \leq 2n \right \} \\[1em] L_2 =\left \{ a^i b^j c^k \mid i=2j \text{ or } j=2k \right \}$$
0 0 votes
2 answers 2 answers
2.9k
2.9k views
sakharam asked Oct 18, 2018
2,869 views
TOC Regular Langauges
Is L= 0n1| n>=0 regular?Is the kleene closure i.e. (L)* regular?
0 0 votes
1 1 answer
1.3k
1.3k views
vkm07 asked Jul 8, 2016
1,313 views
context free langauges
Let L be a Context Free Language. Even(L) is the set of all strings w in L such that |w| is even. What can you say about even(L)?(a) It will be regular(b) It will be cont...