Questions tagged [closure-properties]

Questions about operations on objects of some kind that result in objects of the same kind.

321 questions
Filter by
Sorted by
Tagged with
28 views

PDA kleene star construction

I know how to prove that CFL are closed under kleene star operation using CFG. I can't find online or in class notes a proof using PDA. I would appreciate description of the basic idea (not formal).
43 views

How to show that language L is NOT context-free?

True or false: To show that a language L is not context-free, one can alternatively show that the union between L and a known context-free language is not context-free. I know that you can prove ...
20 views

closure of Context free grammer to homomorphism using PDA

I was looking online, on sipser book, and on lecture notes and I can't find a proof to closure of context free languages to homomorphism that using PDA instead of CFG. I'm not looking for a full and ...
31 views

81 views

24 views

$L = \{\alpha^i \beta^j \gamma^k \vert i,j,k \in \mathbb{N}_0, (i=1) \Rightarrow (j=k)\}$

I am asking this question here, because I am not allowed to comment on the thread that I am actually interested in, but maybe someone can still help me? I alredy found an anwser to the Problem above (...
34 views

Decidability of equality of expressions involving exponentiation

Let's have expressions that are finite-sized trees, with elements of $\mathbb N$ as leaf nodes and the operations {$+,\times,-,/$, ^} with their usual semantics as the internal nodes, with the special ...
131 views

Why L' is not regular?

$$L'=\{ww|w\in L\}$$ I need to give an example of regular language L for which the concatenation of 2's $w$ gives $L'$ which is not regular. How can I give such an example if according to closure ...
148 views

Show that if A is regular, then the subset containing only even language strings, is also regular

A language A, even(A) is the subset of A consisting of those strings in A of even length: even(A) = { x∈A | |x| is even} I need to use closure properties show ...
28 views

Policies for handling symbols leaking out of a lexical scope

Suppose it's possible for a symbol to escape the scope in which it is defined. What are considered the possible policies for handling that? I mean possible in the sense of what choices of language ...
124 views

56 views

Are models of computation closed under composition?

It's common to ask whether a particular class of languages $\mathcal{C} \subseteq \mathcal{P}(\Sigma^*)$, for some alphabet $\Sigma$, is closed under complement, or union, or intersection, or ...
178 views

If $L$ is a regular language then so is $L/a =\{w | wa ∈ L\}$, where $L$ is a language over $\Sigma$ and $a \in \Sigma$

I'm trying to work out a proof by construction that $L/a$ would be regular. $a$ is any final symbol at the end of an accepted string, so I figured the only part of the machine that would have to be ...
89 views

How can the union of two 'context-free but not regular' languages be regular?

I cannot understand how the union of two languages which are context-free but not regular, can result in a regular language: If $L_1$ and $L_2$ are 'context-free but not regular' languages, defined ...
46 views

Intersection of decision problems?

Say we have two problems $\Pi_1\in NP$ and $\Pi_2\in coNP$. Where does $\Pi_1\cap\Pi_2$ live?
128 views

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

i am asking myself the following question: Assuming: A and B are context-free languages, then A - B (difference) must also be context-free language, right? but I do not know how to prove it.
28 views

54 views

if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free

I am having a hard time understanding if this would be true or false, can someone point me in the right direction?
69 views

unambiguous context-free languages and complementation

I was considering the following two natural questions about the relationship between unambiguity and complementation for the class of context-free languages: Is the complement of an unambiguous ...
315 views

If $L$ is a regular language, then $s(L)$ is also regular

...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression. For example, if $L=a^*b$ and $s(a) =ab, s(b) = b^*$, we have $s(L) = (ab)^*b^*$. My ...
168 views

Closure of regular languages under deleting a 1 from each even run of 1s

Let $R$ be a regular set over the alphabet $\{0, 1\}$. Give a machine construction to prove that the set obtained by deleting one 1 from each even length block of 1’s is also regular, and using ...
109 views

Finding if the given language is regular or not

I have the language $$L = \{a^mb^nc^o| \, m + n + o > 5\}$$ where $m,n,o$ are non-negative integers. I have to find whether the language is regular or not. My attempt: I feel it should be non ...
262 views

Finite state automaton for the reverse of the language, and multiple starting states

I am studying about Finite State Automaton, and I found that the when reversing a language (i.e., transforming $L$ to $L^R$), I have to add new start state. Why is that? Also, can a Finite State ...
159 views

Show that RP is closed under concatenation

I'm trying to prove the following problem: Show that $RP$ is closed under concatenation Now, let's say that the two languages are $L_{1}$ and $L_{2}$ (both in $RP$). Then I accept a word iff the ...
332 views

Is the union of NP Complete language and a finite language (in P) NP Complete?

Let there be a language $A$ which is NP complete and language $B$ which is a finite language, is the union of $A \cup B$ NP complete language?
155 views

Have any natural complexity classes been proven not to be closed under complement?

Many important (non-deterministic) complexity classes like NP are believed not to be closed under complement. But have any of them been proven not to be? I'm sure one could construct some contrived ...
40 views

Proving that Pre(L) is regular using automatas: Should I prove that Pre(L) is the semantic of the new automata?

Let $L$ be a regular language, and $Pre(L)$ be the set of all words that are prefix of some word in $L$. Prove that $Pre(L)$ is regular. My proof: Let $M = (\Sigma, Q, \delta, q_0, F)$ be an automata ...
159 views

Proving $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ is a CFL with closure properties [duplicate]

Given a language $L$ over $\Sigma=\{a,b\}$ let us define $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ Prove: if $L$ is regular, then $L'$ is a context free language. I know how to ...
33 views

Dependency of operations of languages

I've struggled in the closure properties of the general class of languages because I couldn't use any automata concept and grammars. In specific, I'm interested in dependency of operations. (The ...
983 views

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

I believe this statement to be true. And here's my reasoning: Based on regular languages properties, the concatenation of two regular languages is regular. And since L′ = L · L, it follows that L′ ...
1k views

Why is the intersection of these two Languages Recursively Enumerable, not Recursive?

I am only several days exposed to computational theory, so my understanding is quite slim: in a question, it says that for a regular language L1 and a recursively enumerable but not recursive language ...
1k views

Class P is closed under concatenation

Proving that Class P is closed under concatenation. The answer is given below: But I do not know why stage 2 is repeated at most O(n), could anyone explain this for me please?