context free

Question

a) L = {0ⁱ1^j2^k | k <= i or k <= j}

its CFL or DCFL?

b)  L is a set of binary complement

what does this mean?

Answer 1

Solution to part a)

Given language   =   {  0ⁱ 1^j  2^k   |    k <= i   or   k <= j }

Now we consider each condition.

According to the condition  " k  <=  i "  ,  we need not bother about 'j' hence it has not involved with stack i.e. 1's need not be pushed into stack for comparision with number of 2's..

Similarly according to the other condition , we need not bother about 'i' hence it has not involved with stack i.e. 0's it need not be pushed into stack for comparision with number of 2's as there is no restriction of number of 0's in this case..

Hence it is not clear whether 0's needed to be pushed to stack or 1's needed to do so..Hence there is non determinism..Hence the given language is not a DCFL but a CFL(NCFL to be precise)..

Solution to part b) :

We complement of a language L  = 

L'    =    Σ*   -   L

which means we have to consider all remaining strings in   Σ*  which are not covered by language L..

So we have to think about the complementary case..

So  there may be 2 cases :

a)  opposite of  ( k <= j   or  k <= i )   :   ( k > i  and  k > j )  which cannot be performed by a stack as we need to keep track of both comparisions at same time..

b)  at least 1 violation of  ordering of 0's , 1's and 2's  : that can be denoted by the following regular expression :

=   (0+1+2)*  (10 +  21 + 20) (0 + 1 + 2)*  

Hence L'   =    {  0ⁱ 1^j  2^k   |    k > i   and   k > j  }   ∪   (0+1+2)*  (10 +  21 + 20) (0 + 1 + 2)*

As the first part is CSL (can be implemented by two stacks but not by 1 stack) and second part is regular but not  Σ* (i.e. (0 + 1 + 2)* ) hence the overall language is a CSL..

Hence L' is a CSL..

Answer 2

DCFL

$L=0^{i}1^{j}2^{k}$

• Push $0,1$ and then on seeing $2$, start poping the stack.
• If all your $2$ are over and still there is something in stack ,no matter $0$ or $1$, your string will be accpeted
• else if your stack becomes empty, reject the string.

Comments

The DPDA u have designed is for the condition "i+j > k" and hence this is not necessarily equal to the condition mentioned in the question..

---

@habib , yes i missed that ..I think then it would be CFL not DCFL because either we have to

• push only $0^{i}$ and check it with $2^{k}$ or 
• push  $1^{j}$ and check it with $2^{k}$