28
Consider Lagrange's four square theorem. It states that if $B = \{1^{n^2}| n \geq 0\}$ then $B^4 = \{1^n | n \geq 0\}$. If $B^2$ is regular, take $A = B$ else take $A = B^2$. Either way, this proves the existence of irregular $A$ such that $A^2$ is regular.
26
There's a significant difference between the question as you pose it and the question posed in the exercise. The question asks for an example of a set of regular languages $L_{1}, L_{2}, \ldots$ such that their union
$$
L = \bigcup_{i=1}^{\infty}L_{i}
$$
is not regular. Note the range of the union: $1$ to $\infty$. Regular languages are closed under finite ...
21
Yes, let $H$ be binary encoding of the halting problem and $A=0H\cup 1\{0,1\}^{\ast}\cup\{\epsilon\}$, $B=1H\cup0\{0,1\}^{\ast}\cup \{\epsilon\}$, then $AB=\{0,1\}^{\ast}$ (why?)
20
The union of infinitely many context-free languages may not be context free. In fact, the union of infinitely many languages can be just about anything: let $L$ be a language, and define for every $l \in L$ the (finite) language $L_l = \{ l \}$. The union over all these languages is $L$. Finite languages are regular, but $L$ may not even be decidable (and ...
16
One can understand your question in two ways, according to the definition of "the complement of CFL".
case A: Complement of CFL is the class of all the languages that are not in CFL. Formally, $$\overline{CFL} = \{ L \mid L\notin CFL\}.$$
In that case, $\overline{CFL}$ is way bigger than $P$, it even has languages that are not in $R$, etc.
But maybe that's ...
15
The idea is to decide nondeterministically at the beginning how much the word is cycled, and have a copy of the automaton for every case. In terms of the automaton, that means that we guess in which state $D$ would have been after consuming a word's prefix (which is a suffix of our input), and start in that state.
Now the construction. For every state $q \...
15
Assume $M$ is a deterministic finite state machine accepting $L$. Feed the word $w$ into $M$, which will land you in some state $q$. Construct a new machine $M'$ which is the same as $M$ but has start state $q$. I claim that $M'$ accepts $w^{-1}L$.
Now prove it.
15
First of all, the question you are asking is open, since an affirmative answer shows that $\sf NP = coNP$. In fact it is one of the most prominent open problems in computer science.
If $\sf P= NP$, then the class $\sf NP$ is closed under complement since $\sf P$ is. If on the other hand $\sf P \not = NP$ then we cannot say whether $\sf NP = coNP$ or not. ...
15
For all of the examples in this answer, I'm taking the alphabet to be $\{0,1\}$. Note that the languages $\emptyset$ and $\{0,1\}^*$ are definitely not NP-complete.
The class of NP-complete languages is not closed under intersection. For any NP-complete language $L$, let $L_0 = \{0w\mid w\in L\}$ and $L_1 = \{1w\mid w\in L\}$. $L_0$ and $L_1$ ...
13
"Effectively closed" means that the family is closed under the operation, and that the closure can be computed by giving an automaton/grammar for it (if the original languages are also given in such an effective representation). E.g., given a finite state automaton, we can actually find an automaton for the complement.
Then it is a natural question, whether ...
13
Note that the languages $\emptyset$, $\{\epsilon\}$ and $\Sigma^*$ are regular. Let $L_2$ be any non-regular language over $\Sigma$.
Union. $\emptyset \cup L_2 = L_2$, which is non-regular; $\Sigma^*\cup L_2 = \Sigma^*$, which is regular.
Intersection. $\Sigma^*\cap L_2 = L_2$; $\emptyset\cap L_2 = \emptyset$.
Subtraction. $\Sigma^*\setminus L_2 = \...
13
I was posting only a hint, then I saw other full answers, so this is a full (hidden) succinct solution :-)
12
This characterization of bounded context-free languages is due to Ginsburg ("The Mathematical Theory of Context-Free Languages"), and appears as Corollary 5.3.1 in his book. For general $k$ there are some restrictions on the semilinear sets, but for $k \leq 2$ these restrictions are always satisfied, and so it is straightforward to deduce that the complement ...
12
The statement is false. Consider the language $L = \{a^n b : n \geq 0\}$. Then $L' = \{ a^n b a^n b : n \geq 0 \}$ is not regular (exercise).
The invalid point in your reasoning is a confusion between the following two languages: $L' = \{ ww : w \in L \}$ and $L'' = \{ w_1w_2 : w_1,w_2 \in L \}$. It is $L''$ which is the concatenation of $L$ with itself. ...
11
Since $|w| < 2007$, the number of strings like $ww^Rw$ is finite. So $A(L)$ is finite for all $L$ and is hence regular.
11
To answer these question, we need allow any $L_2$. So let's think that $L_2$ is a very complex language (say, some undecidable language.)
Lets start from the easy question: $A_l(L)$ (question part 2). Take $L_2$ to be undecidable, and $L=\{\varepsilon\}$. What happens?
(moral: Always check the "extremes": empty $L$, $L=\{\varepsilon\}$ and $L=\Sigma^*$...)...
11
You cannot do it in general.
It would make the complement of your language semi-decidable, like the language itself. Hence they would be both decidable by running both machines in parallel.
Of course, this concerns only the case of semi -decidable languages for which the TM does not always halt for words not in the language.
If you have a decidable ...
11
Suppose that $L_2 = \Sigma^*$ and $L_1$ includes the empty string. Then $L_1 \cdot L_2 = \Sigma^*$, yet $L_1$ doesn't even have to be computable.
10
As an amplification of sdcvvc's hint: You can find a context-free language $L$ such that $A(L) = \{a^m b^m c^m \mid m\geq 0\}$, which as you probably know is not context-free.
So we want to find $L$ such that if $ww\in L$, then $w$ has the form $a^m b^m c^m$. We might as well have $L$ be a sublanguage of $a^*b^*c^*a^*b^*c^*$. Now we just need to put ...
10
Your sources are right, and I am afraid there is only little to add, except formalism. I denote the reverse (mirror) of string $w$ by $w^R$.
If $G$ is a grammar, let $H$ be its reversed, so for production $A\to w$ in $G$ we have $A\to w^R$ in $H$.
Then by induction we show that $A\Rightarrow_G^*w$ iff $A\Rightarrow_H^*w^R$.
(basis) In zero steps we have ...
10
The reason that $A$ is not defined as in NP is that we use a finer notion for NP-completeness, which is mapping (Karp) reductions.
Intuitively, in a Karp reduction, we not only want the problem $A$ to be solvable using an oracle for $B$, but we also require that this oracle is only used once, and only as the very last operation.
Why this notion and not ...
10
This is a common misconception: complexity is not a measure of size. That is, it's not that "bigger" language are harder.
Intuitively, a language becomes harder when it's harder to describe it (TMs being a form of description). For example, as @Yuval Filmus points out in the comments, the language whose description is "everything" is very easy to decide.
...
10
As Shaull noted in the comments, $\{a^n b^n\}$ works. The language is trivially context-free but not regular, so I'll show the complement is context-free. A word which is not of the form $a^n b^n$ is either $a^n b^m$ where $n\neq m$, or not of the form $a^n b^m$ at all. So
$(a+b)^{\ast}-{a^n b^n}=\{a^i b^j: i \neq j\} \cup ((a+b)^{\ast}-a^{\ast} b^{\ast})$
...
10
I looked up Hopcroft and Ullman 1979 and it say on page 281 that it is not closed under reversal. But I found no proof in my very fast look at the relevant chapter.
Searching the web does also give a negative answer, with counter example, on stackoverflow by a member of CS (notation adapted):
$(a+b+c)^*WcW^R$, where $W \in (a+b)^+$; this is non-...
10
Note that the construction for the intersection and union ("and" and "or") of two automata is exactly the same, except for the definition of which states are accepting. The same principle applies to any Boolean combination of any finite set of languages: use the product construction and the appropriate definition of which states should be accepting.
10
The notion of a PDA can be generalized to an $S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA). It consists of
a read-only input tape, surrounded by endmarkers,
a finite state control,
a read-write storage tape of length $S(n)$, where $n$ is the length of the input string, and
a stack
In "Hopcroft/Ullman (1979) Introduction to Automata Theory, Languages, ...
10
Going by the OP's comments, the real question here is not the one in the title, but "Why is the set of regular expressions a context-free (rather than regular) language?"
The reason is simply the occurrence of parentheses in more complex regular expressions like $(a+b)^*b(a+c)^*$. In order for such an expression to be well-formed, the parentheses must be ...
9
Yes, $\mbox{Before}(\beta)$ and $\mbox{After}(\beta)$ are context-free languages. Here's how I would prove it. First, a lemma (which is the crux). If $L$ is CF then:
$\mbox{Before}(L,\beta) = \{ \gamma \ |\ \exists \delta . \gamma \beta \delta \in L \}$
and
$\mbox{After}(L,\beta) = \{ \gamma \ |\ \exists \delta . \delta \beta \gamma \in L \}$
are ...
9
Same holds for the Kleene star (Kleene closure):
set $\text{HP}' = \text{HP} \cup \{0,1\}$ with $HP$ being the halting problem. $\text{HP}'$ is clearly undecidable, and $(\text{HP}')^* = \Sigma^*$, which is regular (thus decidable).
Only top voted, non community-wiki answers of a minimum length are eligible
