# Tag Info

### 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 ...
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 ...
• 278k
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 ...
• 278k
Accepted

• 278k
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 ...
• 30.8k
Accepted

• 278k

### 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' ...
• 29.8k
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,169