As of May 31, 2023, we have updated our Code of Conduct.
21 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; $\...
David Richerby's 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 ...
Ameet Deshpande's 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 :-)
Vor's user avatar
  • 12.4k
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 ...
Yuval Filmus's user avatar
12 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 $\...
David Richerby's 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$) ...
Sarvottamananda's 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 ...
Thomas Klimpel's 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 ...
Klaus Draeger's user avatar
10 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 ...
Rick Decker's user avatar
  • 14.7k
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 ...
Yuval Filmus's 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 ...
David Richerby's user avatar
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 ...
Raphael's user avatar
  • 71.7k
9 votes

Why are DCFL not closed under concatenation or Union whereas CFL is?

DCFL does inherit the closure property of its superset CFL: the union and concatenation of two DCFL languages are CFL. What doesn't hold is that the union and concatenation are necessarily ...
Yuval Filmus's user avatar
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. ...
David Richerby's 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 ...
Hendrik Jan's user avatar
  • 29.1k
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 ...
Terence Hang's 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 = \...
D.W.'s user avatar
  • 152k
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{...
Yuval Filmus's 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 ...
Hendrik Jan's user avatar
  • 29.1k
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 ...
Hendrik Jan's user avatar
  • 29.1k
7 votes
Accepted

Myhill-Nerode and closure properties

I do closure under boolean operations with the MyHill-Nerode characterisation. Never saw it done that way. A right congruence $\sim$ saturates a language $L$ if $$ u \sim v \Rightarrow ( u \in L \...
StefanH's user avatar
  • 1,429
7 votes

If $L$ is a regular language then so is $\sqrt{L}=\{w:ww\in L\}$

Here is how to implement your solution. Let $A = \langle Q, q_0, F, \delta \rangle$ be a DFA for $L$. We will construct an NFA $A' = \langle Q', q'_0, F', \delta' \rangle$ as follows: $Q' = \{q'_0\} \...
Yuval Filmus's user avatar
7 votes
Accepted

If L is regular, show that even(L) is also regular

We can also solve this question using closure operations. Let $\Sigma$ be the original alphabet, and let $\Sigma' = \{x' : x \in \Sigma\}$ be a second copy of the alphabet. Define two homomorphisms $h$...
Yuval Filmus's user avatar
7 votes
Accepted

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

No, $L_2L_1$ is not necessarily regular. Let $L_1 = \{0,1\}^*$, which is regular, and $L_2 = \{1\} \cup \{0^n1^n\mid n\geq 1\}$, which is not. Then $L_1L_2$ is the set of all strings ending with&...
David Richerby's user avatar
7 votes
Accepted

Why $A \cap B = \widehat{\widehat{A}\cup \widehat{B}}$ does not holds for the class of Recursively Enumerable Languages?

The claim "If some language class is closed under any two of the three operations namely, Union, Intersection & Complement then it must be closed under the third." is not accurate. I'm not sure ...
D.W.'s user avatar
  • 152k
7 votes
Accepted

Why do we study closure properties of formal languages?

I think that the more fundamental question here is why study specific kinds of formal languages at all. One answer is that formal languages of specific kinds have been found useful in the construction ...
Yuval Filmus's user avatar
7 votes
Accepted

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

By definition, a deterministic finite-state automaton $(Q,\Sigma,\delta,q_0,F)$ must have a total transition function: For every $q \in Q$ and $a \in \Sigma$, $\delta(q,a)$ must be defined. Automaton ...
Hans Hüttel's user avatar
  • 2,486
7 votes

Is the union between a regular language and a random language also a regular language?

The empty language is certainly regular. Take its union with any non-regular language $N$. What's the result?
Rick Decker's user avatar
  • 14.7k
7 votes

Is the difference of two context-free languages still context-free?

The complement of a context-free language $L$ is not necessarily context-free, but it is the difference between two context-free languages ($\Sigma^* - L$). (Here $\Sigma$ is the alphabet of $L$.) ...
rici's user avatar
  • 11.7k
6 votes
Accepted

Prove that regular languages and context-free languages aren't closed under $Perm(L)$

Hints: For regular languages, consider $Perm((01)^*) \cap 0^* 1^*$. For context-free languages, consider $Perm(0^n 1^n 2^m 3^m) \cap 0^* 2^* 1^* 3^*$.
Yuval Filmus's user avatar

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