Awesome q2a theme
+1 vote
Is the following language context-free language(CFL) or not? If yes, then is it Deterministic-CFL (DCFL)?

L={ $a^i b^j$ where $i\neq 2*j+1$ and $j \geq 1$ and $i\geq 1$ }
in Theory of Computation by (10 points) | 34 views

1 Answer

+2 votes
Best answer

$i \neq 2 *j + 1\; means,$

$L=\left \{ a^{i}b^{j} | i>2*j+1 \; or\;i<2*j+1\right \}$

$and\; you \; can \;design \;CFG for\: this \: grammar$

$L1 = \left \{a ^{i}b^{i} \; {|} i > 2\times j+1\right \}\;$

$L2 = \left \{a ^{i}b^{i} \; {|} i < 2\times j+1\right \}$

$And\; do\;L1 \cup L2$

2. Now we need to check whether given Language is DCFL or not due to Union of DCFL languages may not be DCFL.

First step : Modify the Language as L\$. So every string in the language ends with \$ symbol

given i ≥ 1, So on empty stack on encountering first i, push three x symbols into the stack after that change the state Q2.

in this state, if you encounter i, then push two x symbols into the stack but don't change the state. else on encountering j, pop x and change the state Q3.

on Q3, pop x from the stack for each j.

 you have three scenario on Q3:

1) If you encounter \$ on x then move into final state due to i > 2j+1

2) If you encounter j on Z0, then move to final state due to i < 2j+1

3) If you encounter \$ on Z0 then move into non-final state due to i = 2j+1
by (48 points)
selected by

ok, I got it that it is CFL since we can construct NPDA for the same.

But, is there no way to construct DPDA for the given language 'L' like we did 


there is an NPDA for every DPDA but not the vice versa.
What about the language L = { $a^m b^n$ | $m \neq n$ and m,n$\geq 1$ } ? Is this DCFL?


it's not the way to test, is it DCFL or not ? ( i mean it's your intutive idea but not the proper way. )

infact the Language mentioned in the question is DCFL


Whenever you have doubt like whether given language is CFL or not , then append $ to every string of the language, after that analyze is it Deterministic or not ?


My suggestion :

whenever there is '≠' symbol, just keep '=' symbol and test for Deterministic, because Complement of DCFL is DCFL

@Shaik Masthan

1. Can you please elaborate? Are you saying that L = {$a^i b^j$ where i!= 2j+1} is DCFL?

2.It's right that "Complement of DCFL is DCFL".

If we take the language L = {$a^i b^j$ where i=2j+1} which is DCFL .and  take its complement ie.($\sum$* - L).

But it includes the strings like "bb", "bba", "bbaba", "ababab", and so on.. which are not in the language given in the question.

Please correct me if I'm wrong.

I just give an idea but not the exact way

But it includes the strings like "bb", "bba", "bbaba", "ababab", and so on.. which are not in the language given in the question.

on starting state, you can accept/reject the strings by your choice that doesn't affect your answer.


By the way i edited the answer, is it okay for you ?

@Shaik Masthan

Yes, now I got the whole concept. Thanks for introducing the concept of appending '$' to the language..

Btw, just edit the answer one more time since a's and b's are terminals instead of  'i' and 'j'.

@Shaik Masthan

you are right, thank you, sir, to correct me.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Jul 2020
  1. Shaik Masthan

    39 Points

  2. hiteshpujari

    9 Points

  3. fazin

    7 Points

  4. srestha

    7 Points

  5. gaurav2697

    6 Points

  6. Venkatesh Akhouri

    6 Points

  7. Meghana518

    6 Points

  8. athenahermes

    6 Points

  9. bittujash

    6 Points

  10. Pawan_k

    6 Points

7,560 questions
1,783 answers
90,492 users