Dar una gramática regular para L

Question

Dar una gramática regular para $L = \{a^n b^n : n \leqslant 100\}$

Yo haría algo así:

$S \to A \ |\ \text{empty string}$

$A \to aB \ |\ \text{empty string}$

$B \to Ab$

pero ¿Cómo se lleva la cuenta del número en la gramática? es decir ¿Cómo se sabe cuando hay más que $100$ $a$ 's. Además, ni siquiera estoy seguro de que mi manera tenga sentido.

Se agradecería cualquier ayuda.

Answer 1

Una pista: Utilizar los no terminales como memoria. En particular (y esto contempla una gramática regular correcta) para cada $n$ dejar $A_n$ sea un no-terminal lo que significa que (hasta ahora) $n$ $\mathtt{a}$ se han escrito en la cadena, y deja que $B_n$ sea un no-terminal lo que significa que $n$ más $\mathtt{b}$ deben escribirse en la cadena.

Answer 2

Obsérvese que el tipo de gramática que se está considerando no es regular, ya que es "regular a izquierda y derecha", por lo que en realidad es un gramática lineal .

Sin embargo, no se necesita una gramática lineal, ya que $L$ es regular y además es finito Por lo tanto, a partir del lema del bombeo, como la palabra más larga que hay que reconocer tiene una longitud de 200, se puede concluir que el autómata mínimo que reconoce $L$ tiene al menos 201 estados, por lo que no se puede esperar una gramática "pequeña".

Esto es sencillo ( $S$ son los axiomas, $A_1$ , $\ldots$ , $A_{100}$ , $B_1$ , $\ldots$ , $B_{100}$ son no terminales), es una gramática regular correcta:

$S \to aA_1 \ |\ \varepsilon$

$A_1 \to aA_2 \ |\ b$

$A_2 \to aA_3 \ |\ bB_2$

$\ldots$

$A_{99} \to aA_{100} \ |\ bB_{99}$

$A_{100} \to bB_{100}$

$B_{100} \to bB_{99}$

$B_{99} \to bB_{98}$

$\ldots$

$B_{3} \to bB_{2}$

$B_{2} \to b$

Intenta imaginar el autómata descrito por esta gramática (los no terminales son estados, se necesita también un estado extra, digamos $B_1$ que será el estado final).