retagged by
531 views
2 votes
2 votes
  1. $L = \{w \mid w ∈ {a,b}, n_a(w) \geq n_b(w)+1\}$

  2. $L = \{a^ib^j \mid i ≠ 2j+1\}$

  3. $L = \{a^mb^n \mid m=2n+1\}$

NOTE: 1 - DCFL, 2 - DCFL, 3 -DCFL, but need a proper reason!

retagged by

1 Answer

Best answer
5 votes
5 votes

1. L = {w | w ∈ {a,b}, na(w) >= nb(w)+1}

case 1 : first a's come and then b's

push a's

pop a's for every b's , if there is one or more than one a's still then condition satisfied

case 2: first b's come and then a's

push b's

pop b's for every a's , if there is one or more than one a's still then condition satisfied

therefore DCFL

2. L = {aibj | i ≠ 2j+1}

Here only one case - first a's come and then b's

push a's

for every  b pop one 2 a's 

if a single a is left then dont accpet, other everything can be accepted

Therefore DCFL

3. L = {ambn | m=2n+1}

Here only one case - first a's come and then b's

push a's

for every  b pop  2 a's 

if a single a is left then  accept

Therefore DCFL

eg : if n=2 then 2n+1 = 4+1 =5

m=2n+1, therefore m=5

now for  2 m's one n is popped ..therefore now n=1 and m=3

again for  2 m's one n is popped....therefore now n=0 and m=1

Still one m is left therefore condition satisfied

edited by

Related questions

1 votes
1 votes
0 answers
1
iarnav asked Sep 20, 2017
262 views
L = {ab3k | k>=0}wel, I think, this L is RL, as it has REGEX as a(bbb)*.Please correct me.