16 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
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
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
11 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
  • 72.3k
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

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
  • 30.4k
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
  • 30.4k
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
  • 158k
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,439
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

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.8k
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
  • 12k
6 votes

Why are palindrome and not-palindrome both context-free?

You make the mistake of assuming that $\qquad \lnot \forall\, x \in X. P(x) \quad \equiv \quad \forall\, x \in X. \lnot P(x)$ while in truth $\qquad \lnot \forall\, x \in X. P(x) \quad \equiv \...
Raphael's user avatar
  • 72.3k
6 votes
Accepted

Closure properties of the class of inherently ambiguous CFLs

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 ...
Yuval Filmus's user avatar
6 votes

Show that P is closed against the Kleene star

Just extending a bit more what Yuval Filmus has already said. Suppose your input is $x_1\ldots x_n$. Let's use a memorization array $A$, where $A[i]$ is $True$ in case $x_1 \ldots x_i$ is in $L^*$ and ...
Gabriel F. Silva's user avatar
6 votes
Accepted

How to show that a language {w|ww^R in A} is regular, A being regular?

You might want to study If $L$ is a regular language then so is $\sqrt L=\{w\mid ww∈L\}$. The solution is to simulate the DFA in parallel with itself, from both sides of the string. For each letter ...
Hendrik Jan's user avatar
  • 30.4k
6 votes
Accepted

Are the undecidable languages closed under complement?

Suppose you could decide the complement. Wouldn't you then be able to decide the language itself?
David Richerby's user avatar
6 votes

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

The fact that is a proper subset does not inherit the global properties in general is common in mathematics and computer science. A proper subset does not have to inherit the global properties of its ...
fade2black's user avatar
  • 9,817
6 votes

Why can't we say that NP is closed under complement given that we can say it is closed under intersection

There are several ways to describe the semantics of nondeterministic Turing machines. Perhaps the most colorful is the "guess and verify" semantics. We enhance a vanilla Turing machines with ...
Yuval Filmus's user avatar
6 votes
Accepted

Can the regular image of a context-free language be undecidable?

If $L_1$ is context-free, then so is $L_2$. You can show this easily using closure properties of context-free languages. Let $\Sigma' = \{ \sigma' : \sigma \in \Sigma \}$; we assume that $\Sigma$ and $...
Yuval Filmus's user avatar
6 votes

Can the regular image of a context-free language be undecidable?

This is a form of left quotient of a context-free language by a regular language: $L_2 = R\backslash L_1 = \{ x\in \Sigma^* : yx\in L_1 \text{ for some } y\in R \}$, where in your case $R= \Sigma^* \...
Hendrik Jan's user avatar
  • 30.4k
6 votes

Given L is a regular language, prove that Perm(L) is Context-Free

Clearly we cannot keep both the number of $a$'s and the number of $b$'s on the stack, because what order should we use. The solution (I think) is to keep the difference of these numbers on the stack. ...
Hendrik Jan's user avatar
  • 30.4k
5 votes

Proving that PP is closed under symmetric difference

As stated in the Wikipedia article about PP, a proof that PP is closed under symmetric difference was a PhD thesis by David Russo Structural properties of complexity classes. Proving that PP is closed ...
adrianN's user avatar
  • 5,931
5 votes

Proving that PP is closed under symmetric difference

There are several different definitions of $\mathsf{PP}$. I'll take this one: the class of languages $L$ such that there exists a probabilistic polytime Turing machine $T$ satisfying $$L = \{x : \Pr[T(...
Yuval Filmus's user avatar
5 votes

Showing Regular Languages are closed under removal of rightmost character

This is just a special case of right quotient. Specifically, for a language $L$ over an alphabet $\Sigma$, this is $L / \Sigma$. Many textbooks and course notes contain proof of regular languages' ...
Joey Eremondi's user avatar

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