28
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 ...
17
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. ...
17
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 = \...
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
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.
...
13
There is another way to look at this problem.
Consider that the Language $L$ is a CFL. This means that there is a grammar $G=\{N,\sum,P,S\}$ that satisfies the CFL. We can assume that this is in Chomsky Normal Form.
If $\epsilon$ is part of the language, trivially $\epsilon^R$ is also part of the language.
Now for every production of the form $P_1 \...
13
I was posting only a hint, then I saw other full answers, so this is a full (hidden) succinct solution :-)
13
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
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.
11
Because regular langauges are closed under complementation. That is, if $L$ is regular, so is $\overline{L}$. (Exercise: prove this.)
So, suppose that $L$ is non-regular. If its complement $\overline{L}$ were regular, then $\overline{\overline{L}}=L$ would also have to be regular.
11
Yes you are on right track.
We can first define ($A$ avoids $B$) as ($A$ - ($A$ has $B$)), where ($A$ has $B$) are strings of $A$ which contain strings of $B$ as substrings. Then ($A$ avoids $B$) will be strings of $A$ that do not contain strings of $B$ as substrings.
We can define ($A$ has $B$) as $A \cap (\Sigma^* B \Sigma^*)$. Then ($A$ has $B$) are ...
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 ...
10
Let $L_1, L_2$ be languages, then the concatenation $L_1\circ L_2=\{w\mid w=xy, x\in L_1, y\in L_2\}$. If $L_2=\varnothing$, then there is no string $y\in L_2$ and so there is no possible $w$ such that $w=xy$. Thus for any $L_1$, we'll have $L_1\circ\varnothing = \varnothing$.
10
The claim is that the intersection of a regular language and a context-free language is context-free. You've intersected a regular language ($\{ab\}$) and a context-free language ($\{a^nb^n\mid n\geq 0\}$) and the result was a context-free language ($\{a b\}$). Sure, that language is also regular but every regular language is also context-free. The statement ...
9
The first closure property, closure under intersection, is a DIY proof if you choose the right model for the context-sensitive languages. By defining them with the help of linear-bounded automata you can run two of these automata successively to test (nondeterministically) for acceptance of the intersection.
Second, closure under complement, is hard! It ...
9
That is possible, but perhaps not exactly in the way you ask. As a start take the Dyck language $D_2$ of all strings of matching brackets over two pairs of brackets, say $\{ [,], (,) \}$, or more abstractly $a_1,b_1,a_2,b_2$.
Then every context-free language can be obtained from $D_2$ using homomorphisms, inverse homomorphisms and intersection with regular ...
9
Hint: Use dynamic programming. If the input is $x_1 \ldots x_n$, compute inductively whether $x_1 \ldots x_i \in L^*$. Use the fact that you can check whether $x_{j+1} \ldots x_i \in L$ in polynomial time.
9
So when doing the transition table of the two automata, if there is no transition, should I just ignore it like in the 3rd automaton?
If there is no transition in one of the automata, then that one won't accept the input word. Therefore, the automaton for the intersection should not accept either; not having a transition is one way to make sure of that.
8
Let $R$ be a regular language. Then there is a finite automaton $M$ for which the language, $L(M)$, of $M$ is $R$. Without loss of generality, we may assume that $M$ has no unreachable states. Construct a new FA, $M'$, as follows:
For each state $q$ of $M$ which has a sequence of transitions to a final state of $M$, make $q$ a final state. Call the set of ...
8
Suppose there are two words in the language whose lengths are relatively prime. Let these lengths be $x$ and $y$. We know (see this) that by adding these numbers to each other repeatedly, we can get any number greater than $(x - 1)(y - 1) - 1$. So if $x$ and $y$ are $13$ and $7$, we can write any number greater than $72$ as a linear combination of $7$ and $...
8
The intuition developed in the comments is right. The answer is NO, there is a counter-example, a CFL for which the first halves are not CFL.
$L = \{ a^m b^n c^n a^{3m} \mid m,n\ge 1 \}$, over the alphabet $\{a,b,c\}$, from the answer on our sister site.
A slight adaptation of that language is
$K = \{ a^m b^n c^n \#\# a^{3m} \mid m,n\ge 1 \}$, over the ...
8
Let $f$ be a bijective function, which is not primitive recursive. We know, that such a function exists. Let further be $g=f^{-1}$ the inverse function of $f$. Therefore $f\circ g$ is the identity function, which is clearly primitive recursive.
8
You can't prove it because it isn't true: the class of non-regular languages isn't closed under concatenation.
Let $X\subseteq \mathbb{N}$ be any undecidable set containing $1$ and every even number. For example, take your favourite undecidable set $S$ and let $$X = \{0, 2, 4, \dots\} \cup \{1\} \cup \{2i+1\mid i\in S\}\,.$$ The language $\mathcal{L} =...
8
For our readers. Linear grammars are close to regular grammars, a single nonterminal at the time, but they may generate letters at both sides $A \to aBb$ with $A,B$ nonterminal, and $a,b$ terminal (or empty). $REG \subset LIN \subset CF$, strict.
Some closure proofs may benefit from another way to define linear languages: as single turn pushdown languages.
...
8
Is an irregular language concatenated with a language with which it has no common symbols irregular?
First, your $L1L2$ is wrong. $$L1L2 = \{a^ib^ic^j\ | \ i>0, j>0\}$$
Your conclusion is right, $L1L2$ is irregular(as long as $L2\neq\phi$, otherwise $L1L2=\phi$ is clearly regular). This can be proved using Myhill–Nerode theorem.
Suppose $X$,$Y$ are any 2 different equivalence classes of $R_{L1}$, $x\in X, y\in Y$, then there exists string $z$ such ...
Only top voted, non community-wiki answers of a minimum length are eligible