19
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 ...
- 293
14
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 ...
- 279k
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 ...
- 72.9k
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 ...
- 279k
8
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\} \...
- 279k
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 ...
- 31.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 \...
- 1,469
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 ...
- 2,516
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?
- 14.9k
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$.)
...
- 12.1k
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 ...
- 31.1k
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 ...
- 310
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?
- 82.2k
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 ...
- 9,885
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 ...
- 279k
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 $...
- 279k
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^* \...
- 31.1k
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. ...
- 31.1k
5
votes
Accepted
Inverse Homomorphisms and Kleene star
Since you solved the first question, let me answer the second one. If you don't mind, I will use $h$ instead of $h'$ for simplicity. Let $L$ be a regular language and let $K = h^{-1}(L^*)$. Since ...
- 6,189
5
votes
Why can't we say that NP is closed under complement given that we can say it is closed under intersection
Nondeterministic Turing Machines don't technically reject. They accept or run indefinitely. You can also not abort that. It's a very subtle difference with a lot of impact. Otherwise indeed it would ...
- 2,511
5
votes
Accepted
context free grammar not closed under relative complement using product construction of pda and dfa
If you forget about the product-part of this construction (or just consider $L_2=\Sigma^*$) then your proposal amounts to swapping the accepting states of the pushdown automaton. The new PDA has an ...
- 31.1k
5
votes
Accepted
Given L is a regular language, prove that Perm(L) is Context-Free
For every symbol $\sigma_i$ that the PDA reads, it guesses a symbol $\tau_i$. It simulates the DFA on the word $\tau_1 \ldots \tau_i$, and will only accept if the DFA accepts. Using the stack, it ...
- 279k
5
votes
Is the set of languages satisfying the pumping lemma closed under concatenation?
Suppose that $L_1$ satisfies the pumping lemma: there exists $p_1$ such that every word $w \in L_1$ of length at least $p$ can be decomposed as $w = xyz$, where $|xy| \leq p_1$, $y \neq \epsilon$, and ...
- 279k
5
votes
Accepted
context-free shuffle for two-letter alphabets
Two letters should be sufficient as the following example shows: let
$L_1=\{a^nba^n\mid n\geq1\}$ and $L_2=\{b^nab^n\mid n\geq1\}$. Then we have $$(L_1\|L_2)\cap a^*b^*a^*b^*=\{a^mb^{n+1}a^{m+1}b^n\...
- 166
5
votes
Does there exist an context free language L such that L∩L^R is not context free?
Consider $L = \{ a^n b^n a^m \mid m,n\ge 1\}$.
In fact you can repeat this to get more equalities $\{ a^n b^n a^m b^m a^k \mid k,m,n\ge 1\}$. Etcetera.
Note that we can get really fun things:
For
$ L ...
- 31.1k
5
votes
Accepted
Give a class of languages which is closed under intersection and union, but not under complement
An example of a class of languages which is closed under union and intersection, but not under complement is the class of finite languages.
Context-free languages are closed under union, but not under ...
- 31.1k
4
votes
Context-free Languages closed under Reversal
First off. CFL's are not closed under intersection or complement (or difference for that matter). They are closed under Union, Concatenation, Kleene star closure, substitution, homomorphism, inverse ...
- 141
4
votes
Is the union between a regular language and a random language also a regular language?
Suppose L1 = a* (regular language) and L2=anbn, where n is a natural number (L2 is not regular).
L = L1 U L2 = {ε, a, aa, aaa, ..., ab, aabb, aaabbb, ... } but there is no DFA able to recognize words ...
- 591
4
votes
Accepted
Closure operator and set of fixpoint
There is an intimate connection between closure operators and complete lattices.
Given a closure operator $C$ on a set $X$, we can construct a complete lattice $L(C)$ as follows:
The points of the ...
- 279k
4
votes
Accepted
Closure property of recursively enumerable language
Basically, "R.e. sets are closed under intersection means that for any two r.e. sets $A \cap B$ is again r.e, but when we say that r.e. are not closed under some set-theoretic operation it means there ...
- 9,885
Only top scored, non community-wiki answers of a minimum length are eligible