+1 vote
33 views
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$ }
| 33 views

Here,

$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
0

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

here: https://qr.ae/pNK9ZH

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

@RavGopal

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 0 @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. 0 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 ? 0 @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'.

Thanks..
0
@Shaik Masthan

you are right, thank you, sir, to correct me.