patternMinor
Closure properties of the class of inherently ambiguous CFLs
Viewed 0 times
cflsthepropertiesinherentlyambiguousclassclosure
Problem
is set of inherently ambiguous context free languages close under operations such that union, intersection, kleene star, concatenation, reverse, complementation and etc. how many of theme are answered?
Solution
Reversal
The class of inherently ambiguous context-free languages is closed under reversal (exercise).
Intersection
The class of inherently ambiguous context-free languages is not closed under intersection. Indeed, take some inherently ambiguous context-free language $L$. Now take $L'$ to be a copy of $L$ which uses a different alphabet. Then $L \cap L' = \emptyset$.
Complementation
The class of inherently ambiguous context-free languages is not closed under complementation. Indeed, consider the Goldstine language
$$ G = \{ a^{n_1} b \cdots a^{n_p} b : p \geq 1 \text{ and } n_i \neq i \text{ for some } i \}. $$
This language is context-free and inherently ambiguous (see slides of Cyril Nicaud). Also,
$$
\overline{G} \cap \Sigma^* b = \{ aba^2\cdots a^p b : p \geq 1 \},
$$
which isn't even context-free.
Union
The class of inherently ambiguous context-free languages is not closed under union. Indeed, the following variant of the Goldstine language is probably also context-free and inherently ambiguous:
$$ G' = \{ a^{n_1} b \cdots a^{n_p} b : p \geq 1 \text{ and } n_i \neq i+1 \text{ for some } i \}. $$
However, $G \cup G' = (a^*b)^+$.
Iteration (Kleene star)
The class of inherently ambiguous context-free languages is not closed under Kleene star. Indeed, consider the following language:
$$
\Omega_3 = \{ u \in \{a,b,c\}^* : |u|_a \neq |u|_b \text{ or } |u|_a \neq |u|_c \}.
$$
Here $|u|_a$ is the number of $a$s in $u$. This language is context-free and inherently ambiguous (see the slides of Cyril Nicaud). However, $\Omega_3^ = \{a,b,c\}^$.
Concatenation
The class of inherently ambiguous context-free languages is not closed under concatenation. Indeed, the following variants of $\Omega_3$ are probably also context-free and inherently ambiguous:
$$
\begin{align*}
\Omega'_3 &= \{ u \in \{a,b,c\}^* : |u|_a \neq |u|_b \text{ or } |u|_a \neq |u|_c \text{ or } u = \epsilon \}, \\
\Omega''_3 &= \{ u \in \{a,b,c\}^* : |u|_a \neq |u|_b+1 \text{ or } |u|_a \neq |u|_c+1 \text{ or } u = \epsilon \}.
\end{align*}
$$
However, $\Omega'_3 \Omega''_3 = \{a,b,c\}^*$.
The class of inherently ambiguous context-free languages is closed under reversal (exercise).
Intersection
The class of inherently ambiguous context-free languages is not closed under intersection. Indeed, take some inherently ambiguous context-free language $L$. Now take $L'$ to be a copy of $L$ which uses a different alphabet. Then $L \cap L' = \emptyset$.
Complementation
The class of inherently ambiguous context-free languages is not closed under complementation. Indeed, consider the Goldstine language
$$ G = \{ a^{n_1} b \cdots a^{n_p} b : p \geq 1 \text{ and } n_i \neq i \text{ for some } i \}. $$
This language is context-free and inherently ambiguous (see slides of Cyril Nicaud). Also,
$$
\overline{G} \cap \Sigma^* b = \{ aba^2\cdots a^p b : p \geq 1 \},
$$
which isn't even context-free.
Union
The class of inherently ambiguous context-free languages is not closed under union. Indeed, the following variant of the Goldstine language is probably also context-free and inherently ambiguous:
$$ G' = \{ a^{n_1} b \cdots a^{n_p} b : p \geq 1 \text{ and } n_i \neq i+1 \text{ for some } i \}. $$
However, $G \cup G' = (a^*b)^+$.
Iteration (Kleene star)
The class of inherently ambiguous context-free languages is not closed under Kleene star. Indeed, consider the following language:
$$
\Omega_3 = \{ u \in \{a,b,c\}^* : |u|_a \neq |u|_b \text{ or } |u|_a \neq |u|_c \}.
$$
Here $|u|_a$ is the number of $a$s in $u$. This language is context-free and inherently ambiguous (see the slides of Cyril Nicaud). However, $\Omega_3^ = \{a,b,c\}^$.
Concatenation
The class of inherently ambiguous context-free languages is not closed under concatenation. Indeed, the following variants of $\Omega_3$ are probably also context-free and inherently ambiguous:
$$
\begin{align*}
\Omega'_3 &= \{ u \in \{a,b,c\}^* : |u|_a \neq |u|_b \text{ or } |u|_a \neq |u|_c \text{ or } u = \epsilon \}, \\
\Omega''_3 &= \{ u \in \{a,b,c\}^* : |u|_a \neq |u|_b+1 \text{ or } |u|_a \neq |u|_c+1 \text{ or } u = \epsilon \}.
\end{align*}
$$
However, $\Omega'_3 \Omega''_3 = \{a,b,c\}^*$.
Context
StackExchange Computer Science Q#55297, answer score: 6
Revisions (0)
No revisions yet.