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
327 views

Is NEXP = co-NEXP?

It is known that $\mathsf{NL}=\mathsf{Co{-}NL}$ and unknown if $\mathsf{NP}=\mathsf{Co{-}NP}$. But what about $$\mathsf{NEXP}=\mathsf{Co{-}NEXP}?$$ Is it known whether these two classes are equal?
429 views

Regularity of “middles” of words from regular language

I need some help with the following problem. Let $L \subseteq \Sigma^*$ be a regular language. I have to prove that the language $P = \{\alpha \mid \beta\alpha\gamma \in L, \beta,\gamma \in \Sigma^*\}$...
130 views

Finding the mistake(s) within this “proof” of NP being closed for complement

For my classes in theoretical computer science the following proof must be shown to be wrong. However, this is the first time I am attempting myself at this topic, so I would be thankful for some help:...
350 views

Why do we study closure properties of formal languages?

In automata theory we study formal languages like Regular, CF, CS and etc. and each of them have their own closure properties under union, intersection, star and etc. . I like to know, why it is ...
354 views

Closure properties of the class of inherently ambiguous CFLs

is set of inherently ambiguous context free languages close under operations such that union, intersection, kleene star, concatenation, reverse, complementation and etc. how many of theme are answered?...
3k views

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

Both palindrome and its complement are context-free. This is very interesting. Both are non-deterministic context-free, which in general are not closed under complement. What is it about these two ...
145 views

If a language is X-complete, is its complement is X-complete as well?

I'm looking for an information about closure of complexity complete classes. Is it true that any language, if the language is X-complete, then its complement is X-complete? Why? I was thinking ...
58 views

How to prove that the decidable languages are closed against iteration only by enumerators?

We have the $L\in R$, how can we prove that $L^*\in R$ only by enumerators? I try to use induction, but as I understand I wrong... I'd like to get any help!
2k views

Closure under reversal of regular languages: Proof using Automata

I have been studying the closure properties of regular languages, referencing the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman. Under the ...