4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Apr 1 '16 at 17:20
  • 1
    $\begingroup$ It's hard problem for homework. I don't think there is a university in world that ask this problem for bachelor of science student. a problem over class of languages that membership of it is undecidable. I was study closure if regular, deterministic context free, linear grammar and RE and R and etc. there was no topic and problem such this in Peter Linz and Michael Sipser book. and of course I pass Introduction to computation theory and theory of computation courses in university. so I don't have homework. I was just interesting in this problem while rereading Peter Linz book. @Raphael $\endgroup$ – Karo Apr 1 '16 at 17:35
  • $\begingroup$ and there is similar question in cs stackexchange link if there is some reference that could help me find answer tell me and introduce some books. @Raphael $\endgroup$ – Karo Apr 1 '16 at 17:38
6
$\begingroup$

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\}^*$.

$\endgroup$
  • $\begingroup$ Hm. Is there an easy way to get a feeling that there should be not too many closure properties? For instance, IACFL is not closed against intersection with regular languages ($G \cap a^*b$) which is a very basic one; do any of these follow? I guess what I'm asking is: how do closure properties relate? Maybe I should ask this in a new post. $\endgroup$ – Raphael Apr 2 '16 at 12:54
  • $\begingroup$ The main idea here is that there is absolutely no reason to expect that IACFL be closed under any non-trivial operation. All you need is a reservoir of examples, and with some work you should be able to find counterexamples. It is certainly possible that you can significantly simplify the counterexamples I list; I didn't try to optimize them at all. What you're suggesting is whether there is one key property which implies many of these non-closure results, and that's indeed an interesting question, though you'd have to come up with more examples of relevant language classes. $\endgroup$ – Yuval Filmus Apr 2 '16 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.