Skip to main content

If you settle for a noncontracting (or monotonic) grammar instead:

$S\to DTA \mid ab$ $~~~~~$ the last $A$ is an end-marker for the last $ab^n$, $n=1$ separate.

$T\to DTa \mid Da$ $~~~~~$ number of $D$'s equals the number of $a$'s ($A$ counts as $a$)

$Da \to abD$ $~~~~~$ every $a$ gets an extra $b$

$Db \to bD$ $~~~~~$ $D$ moves over $b$'s

$DA \to Ab$ $~~~~~$ and $D$ disappears at the last block of $ab^n$

$A \to a$ $~~~~~$ finally end-marker $A$ is changed into $a$ (if we do this too soon, the $D$'s will not disappear, and the dirivation is not valid)


Example of building word $abbbabbbabbb$ ($n=3$) (added by @Andremoniy):

  1. $S\Rightarrow DTA\Rightarrow DDTaA\Rightarrow DDDaaA$ - "inflate" string $n$ times;

  2. $\Rightarrow DDabDaA\Rightarrow DabDbDaA\Rightarrow abDbDbDaA\Rightarrow abbDDbDaA\Rightarrow abbbDDDaA\Rightarrow \dots$ - we built 1st subword $abbb$, move on

  3. $\Rightarrow abbbDDabDA\Rightarrow abbbDabDbDA\Rightarrow abbbabDbDbDA\Rightarrow abbbabbbDDDA\Rightarrow\dots$ - two subwords $abbbabbb$ are built, move on

  4. $\Rightarrow abbbabbbDDAb\Rightarrow abbbabbbDAbb\Rightarrow abbbabbbAbbb\Rightarrow abbbabbbabbb$

If you settle for a noncontracting (or monotonic) grammar instead:

$S\to DTA \mid ab$ $~~~~~$ the last $A$ is an end-marker for the last $ab^n$, $n=1$ separate.

$T\to DTa \mid Da$ $~~~~~$ number of $D$'s equals the number of $a$'s ($A$ counts as $a$)

$Da \to abD$ $~~~~~$ every $a$ gets an extra $b$

$Db \to bD$ $~~~~~$ $D$ moves over $b$'s

$DA \to Ab$ $~~~~~$ and $D$ disappears at the last block of $ab^n$

$A \to a$ $~~~~~$ finally end-marker $A$ is changed into $a$ (if we do this too soon, the $D$'s will not disappear, and the dirivation is not valid)

If you settle for a noncontracting (or monotonic) grammar instead:

$S\to DTA \mid ab$ $~~~~~$ the last $A$ is an end-marker for the last $ab^n$, $n=1$ separate.

$T\to DTa \mid Da$ $~~~~~$ number of $D$'s equals the number of $a$'s ($A$ counts as $a$)

$Da \to abD$ $~~~~~$ every $a$ gets an extra $b$

$Db \to bD$ $~~~~~$ $D$ moves over $b$'s

$DA \to Ab$ $~~~~~$ and $D$ disappears at the last block of $ab^n$

$A \to a$ $~~~~~$ finally end-marker $A$ is changed into $a$ (if we do this too soon, the $D$'s will not disappear, and the dirivation is not valid)


Example of building word $abbbabbbabbb$ ($n=3$) (added by @Andremoniy):

  1. $S\Rightarrow DTA\Rightarrow DDTaA\Rightarrow DDDaaA$ - "inflate" string $n$ times;

  2. $\Rightarrow DDabDaA\Rightarrow DabDbDaA\Rightarrow abDbDbDaA\Rightarrow abbDDbDaA\Rightarrow abbbDDDaA\Rightarrow \dots$ - we built 1st subword $abbb$, move on

  3. $\Rightarrow abbbDDabDA\Rightarrow abbbDabDbDA\Rightarrow abbbabDbDbDA\Rightarrow abbbabbbDDDA\Rightarrow\dots$ - two subwords $abbbabbb$ are built, move on

  4. $\Rightarrow abbbabbbDDAb\Rightarrow abbbabbbDAbb\Rightarrow abbbabbbAbbb\Rightarrow abbbabbbabbb$

added 44 characters in body
Source Link
Hendrik Jan
  • 31.1k
  • 1
  • 54
  • 107

If you settle for a noncontracting (or monotonic) grammar instead:

$S\to DTA \mid ab$ $~~~~~$ the last $A$ is an end-marker for the last $ab^n$, $n=1$ separate.

$T\to DTa \mid Da$ $~~~~~$ number of $D$'s equals the number of $a$'s ($A$ counts as $a$)

$Da \to abD$ $~~~~~$ every $a$ gets an extra $b$

$Db \to bD$ $~~~~~$ $D$ moves over $b$'s

$DA \to Ab$ $~~~~~$ and $D$ disappears at the last block of $ab^n$

$A \to a$ $~~~~~$ finally end-marker $A$ is changed into $a$ (if we do this too soon, the $D$'s will not disappear, and the dirivation is not valid)

If you settle for a noncontracting (or monotonic) grammar instead:

$S\to DTA \mid ab$ $~~~~~$ the last $A$ is an end-marker for the last $ab^n$, $n=1$ separate.

$T\to DTa \mid Da$ $~~~~~$ number of $D$'s equals the number of $a$'s ($A$ counts as $a$)

$Da \to abD$ $~~~~~$ every $a$ gets an extra $b$

$DA \to Ab$ $~~~~~$ and $D$ disappears at the last block of $ab^n$

$A \to a$ $~~~~~$ finally end-marker $A$ is changed into $a$ (if we do this too soon, the $D$'s will not disappear, and the dirivation is not valid)

If you settle for a noncontracting (or monotonic) grammar instead:

$S\to DTA \mid ab$ $~~~~~$ the last $A$ is an end-marker for the last $ab^n$, $n=1$ separate.

$T\to DTa \mid Da$ $~~~~~$ number of $D$'s equals the number of $a$'s ($A$ counts as $a$)

$Da \to abD$ $~~~~~$ every $a$ gets an extra $b$

$Db \to bD$ $~~~~~$ $D$ moves over $b$'s

$DA \to Ab$ $~~~~~$ and $D$ disappears at the last block of $ab^n$

$A \to a$ $~~~~~$ finally end-marker $A$ is changed into $a$ (if we do this too soon, the $D$'s will not disappear, and the dirivation is not valid)

Source Link
Hendrik Jan
  • 31.1k
  • 1
  • 54
  • 107

If you settle for a noncontracting (or monotonic) grammar instead:

$S\to DTA \mid ab$ $~~~~~$ the last $A$ is an end-marker for the last $ab^n$, $n=1$ separate.

$T\to DTa \mid Da$ $~~~~~$ number of $D$'s equals the number of $a$'s ($A$ counts as $a$)

$Da \to abD$ $~~~~~$ every $a$ gets an extra $b$

$DA \to Ab$ $~~~~~$ and $D$ disappears at the last block of $ab^n$

$A \to a$ $~~~~~$ finally end-marker $A$ is changed into $a$ (if we do this too soon, the $D$'s will not disappear, and the dirivation is not valid)