¿Puede una gramática regular ambigua?

Question

Una gramática ambigua es una gramática independiente del contexto para el cual existe una cadena que tiene más de una derivación más a la izquierda, mientras que un inequívoco de la gramática es una gramática independiente del contexto para el que cada cadena válida tiene una única derivación más a la izquierda.

Una gramática regular es un objeto matemático, $G$, con cuatro componentes, $G = (N, \Sigma, P, S)$, donde

• $N$ es un vacío, conjunto finito de no terminal símbolos,
• $\Sigma$ es un conjunto finito de símbolos terminales, o alfabeto de símbolos,
• $P$ es un conjunto de reglas de la gramática, cada uno con uno de los formularios:
  • $A \rightarrow aB$
  • $A \rightarrow a$
  • $A \rightarrow \varepsilon$ para $A, B \in N$, $a \in Σ$, y $\varepsilon$ la cadena vacía, y
• $S ∈ N$ es el símbolo inicial.

Ahora la pregunta es: ¿se Puede regular la gramática también ser ambiguo?

Answer 1

Sin duda existen ambiguas gramáticas regulares. Tomemos por ejemplo

$S\rightarrow A~|~B$

$A\rightarrow a$

$B\rightarrow a$

Answer 2

Todos los regulares de la gramática que contiene una regla de la forma $A \rightarrow aB$ (accesible desde el símbolo inicial) tiene un equivalente ambigua regular de la gramática. Se acaba de tomar un nuevo símbolo no terminal, $D$, agregar la regla de $A \rightarrow aD$, y para cada regla con $B$ como la izquierda del símbolo de agregar una nueva regla obtenidos mediante la sustitución de cada una de las $B$ en regla con $D$.

Por ejemplo, los siguientes regular la gramática es ambigua:

$$\begin{align} S &\rightarrow aS \mid bA \\ A &\rightarrow bA \mid aB \mid \varepsilon \\ B &\rightarrow aB \mid \varepsilon \end{align}$$

Tomando la regla de $A \rightarrow aB$ podemos construir un equivalente ambigua regular la gramática de la siguiente manera: $$\begin{align} S &\rightarrow aS \mid bA \\ A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\ B &\rightarrow aB \mid \varepsilon \\ D &\rightarrow aD \mid \varepsilon \end{align}$$

A continuación, la cadena de $ba$ tiene dos derivaciones más a la izquierda:

• $S \rightarrow bA \rightarrow baB \rightarrow ba \varepsilon = ba$
• $S \rightarrow bA \rightarrow baD \rightarrow ba \varepsilon = ba$