2
$\begingroup$

Consider the language: $L = \{0^m1^n : m \neq n - 1 \}$ where $m, n \geq 0$
I tried for hours and hours but couldn't find its context free grammar. I was stuck with a rule which can check on the condition $m \neq n - 1$. Would anyone can help me out? Thanks in advance.

  • 0
    @$A$safKaragila, sorry about that. Really didn't look at the dates.2013-02-09

3 Answers 3

0

we have 3 basic ways to check if a grammar is CFL,

  1. draw a PDA
  2. pumping lemma
  3. get a stack, and check if by 2 operations(push/pop) u can achieve the target

I will go with the stack method here,

we need 0 or more 0s followed by 0 or more 1s, given that no of 0s should not be 1 less than the no of 1s.

Sol:-

  • try pushing as many 0s as you get.

  • once you receive 1, start popping the 0s(if any)

  • at the end of the input,

    if there exists a single 0 in the stack, reject the string else, accept the string.

3

Write grammars for languages $\{0^m 1^n \colon m < n-1\}$ and $\{0^m 1^n \colon m > n-1\}$ and create their sum. As a simplification, you can try to write grammar for $\{0^m 1^n \colon m \leq n\}$ first.

2

The trick is that you need extra "clock" letters $a,b, \dots$ in the language with non-reversible transformations between them, to define the different phases of the algorithm that builds the string. When the first phase is done, transform $a \to b$, then $b \to c$ after phase 2, etc, then finally remove the extra letters to leave a 0-1 string. The natural place for these extra markers is between the 0's and the 1's, or before the 0's, or after the 1's.

The string can be built by first deciding whether $m - (n-1)$ will be positive or negative, then building a chain of 0's (resp. 1's) of some length, then inserting 01's in the "middle" of the string several times. Each of these steps can be encoded by production rules using extra letters in addition to 0 and 1.

  • 0
    Sorry for the late reply, I finally figured it out. Thank you.2011-08-21