29 votes
Accepted

Union of regular languages that is not regular

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 ...
user avatar
20 votes
Accepted

Union and intersection of a regular and a non-regular language

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; $\...
user avatar
17 votes

Is the class NP closed under complement?

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$, ...
user avatar
  • 11.9k
16 votes
Accepted

are NP Complete languages closed under any regular operations?

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 ...
user avatar
14 votes

Context-free Languages closed under Reversal

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 ...
user avatar
13 votes

If $L_1L_2$ is regular language then is $L_2L_1$ regular too?

I was posting only a hint, then I saw other full answers, so this is a full (hidden) succinct solution :-)
user avatar
  • 12.2k
13 votes
Accepted

Proving that if L is regular. Then L′ = {ww : w ∈ L} is regular

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 ...
user avatar
11 votes

If both the concatenation of two languages and the second "half" are regular, is the first too?

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.
user avatar
11 votes

Why is the complement of a language that is not regular also not regular?

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 $\...
user avatar
11 votes
Accepted

Proving $A$ avoiding $B$ regular if $A$ and $B$ are regular

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$) ...
user avatar
  • 4,747
10 votes
Accepted

Constructing all context-free languages from a set of base languages and closure properties?

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 ...
user avatar
  • 27.6k
10 votes
Accepted

Are DCFLs closed under reversal?

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 ...
user avatar
  • 19.1k
10 votes
Accepted

How to XOR automata?

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 ...
user avatar
10 votes
Accepted

Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model

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 ...
user avatar
10 votes
Accepted

Why is the set of all regular expressions classified as context-free, instead of regular?

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 ...
user avatar
10 votes
Accepted

Show that P is closed against the Kleene star

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 ...
user avatar
10 votes
Accepted

Is intersection of regular language and context free language is "always" context free language

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 ...
user avatar
9 votes
Accepted

Why does the concatenation of the empty set with any language give the empty set?

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 ...
user avatar
  • 14.6k
9 votes

Should two DFAs be complete before making an intersection of them?

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 ...
user avatar
  • 70.9k
8 votes
Accepted

Situations where Kleene star of A is context-free, but A is not

Let $L$ be any non-context-free language, then we can construct the language $A = \Sigma\cup L$ - i.e. $A$ is either an element of $\Sigma$ or a string from $L$ (these can happily overlap too). This ...
user avatar
8 votes

Regularity of “middles” of words from regular language

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. ...
user avatar
  • 14.6k
8 votes
Accepted

If L is context-free, must FH(L) be context-free?

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 ...
user avatar
  • 27.6k
8 votes

If $g ∘ f$ is primitive recursive, are $f$ and $g$, too?

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 ...
user avatar
  • 994
8 votes
Accepted

Proving that non-regular languages are closed under concatenation

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. ...
user avatar
8 votes

Closure properties of linear context-free languages

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 ...
user avatar
  • 27.6k
8 votes
Accepted

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 ...
user avatar
8 votes

Is an irregular language concatenated with a language with which it has no common symbols irregular?

Yes: in general, if $L_1$ is a non-regular language over alphabet $\Sigma_1$, and $L_2$ is a language over some other alphabet $\Sigma_2$ with no symbols in common (i.e., $\Sigma_1 \cap \Sigma_2 = \...
user avatar
  • 141k
8 votes
Accepted

Is NEXP = co-NEXP?

It is known that $\mathsf{NP} = \mathsf{coNP}$ implies $\mathsf{NEXP} = \mathsf{coNEXP}$, using a padding argument. However, both are considered unlikely. The difference between classes like $\mathsf{...
user avatar
8 votes
Accepted

Why DCFL is not closed under kleene star?

The language $\{a^nb^nc^k \mid n,k \ge 1\} \cup \{a^nb^kc^n \mid n,k \ge 1\}$ I believe is a standard example of a non-deterministic context-free language. At least intuitively it is clear that we can ...
user avatar
  • 27.6k
8 votes
Accepted

For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular?

Assume we have automaton $\mathcal A$ for regular language $L(\mathcal A) = L$. It is possible to construct a new finite automaton for the new language $L'=\{xy^Rz\mid xyz\in L\}$. You need ...
user avatar
  • 27.6k

Only top scored, non community-wiki answers of a minimum length are eligible