All Questions
Tagged with complexity-theory formal-languages
100 questions
50
votes
2
answers
10k
views
What is the difference between an algorithm, a language and a problem?
It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
- 30.1k
18
votes
3
answers
3k
views
Decidable non-context-sensitive languages
It is arguable that most languages created to describe everyday problems are context-sensitives. In the other hand, it is possible and not hard to find some languages that are not recursive or even ...
- 1,212
14
votes
3
answers
2k
views
Why use languages in Complexity theory
I'm just starting to get into the theory of computation, which studies what can be computed, how quickly, using how much memory and with which computational model.
I have a pretty basic question, but ...
- 241
14
votes
1
answer
1k
views
Computational complexity vs. Chomsky hierarchy
I'm wondering about the relationship between computational complexity and the Chomsky hierarchy, in general.
In particular, if I know that some problem is NP-complete, does it follow that the ...
- 630
13
votes
2
answers
2k
views
What is the complexity of the emptiness problem for 2-way DFAs?
I'm wondering, what is the time-complexity of determining emptiness for 2-way DFAs? That is, finite automata which can move backwards on their read-only input tape.
According to Wikipedia, they are ...
- 30.1k
12
votes
3
answers
24k
views
What is complement of Context-free languages?
I need to know what class of CFL is closed under i.e. what set is complement of CFL.
I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I ...
- 123
12
votes
2
answers
610
views
What is the closure of context-free languages under finite intersections?
Famously the intersection of context-free languages need not be context-free. On the other hand the intersection of context-sensitive languages is context-sensitive.
So this leads to the question: ...
- 121
9
votes
1
answer
1k
views
What are appropriate isomorphisms between formal languages?
A formal language $L$ over an alphabet $\Sigma$ is a subset of $\Sigma^*$, that is, a set of words over that alphabet. Two formal languages $L$ and $L'$ are equal, if the corresponding sets are ...
- 5,400
8
votes
2
answers
1k
views
Please explain "decidability" and "verifiability"
I am trying to (intuitively) understand the two terms "decidability" and "verifiability".
I have done a reasonable amount of searching and going through the various texts I can put my hands on. ...
- 367
7
votes
1
answer
3k
views
Complexity Classes (P, NP) vs Language Hierarchies (REC, RE)
NOTE: The statement of this question has a LOT of misconceptions.
Is there any relation between the Complexity Classes (like P or NP) and Language hierarchies (like REC or RE) ?
Form what I ...
- 203
7
votes
3
answers
6k
views
complexity of determining whether a language given by context free grammar is empty
I know that it is decidable problem to check whether given context free grammar represents empty language -- for instance, AFAIR one could convert it to Chomsky normal form, and then check if any word ...
- 171
7
votes
2
answers
132
views
How to find the minimal description for an array?
The following array occupies 10000 slots in memory:
a = [0,1,2,3,4,5,6,7,8,9,10,...,10000]
But one could easily represent the same array as:
...
- 441
7
votes
2
answers
251
views
Classes of NFAs which allow efficient subset testing or unambiguity conversions
I'm doing some research regarding NFAs and inclusion problems with them. I know that in general, the inclusion problems, and converting to an unambiguous NFA, are both PSPACE-complete.
I'm wondering, ...
- 30.1k
7
votes
1
answer
588
views
Is the closure of P under e-free homomorphisms equal to NP?
The context free languages can be obtained as the closure of the Dyck language under the cone operations. The Dyck language $D_2$ is a deterministic context free language, and the cone operations ...
- 5,400
6
votes
2
answers
121
views
What is the field studying the search and generation of computer programs?
This Github repo hosts a very cool project where the creator is able to, give an integer sequence, predict the most likely next values by searching the smallest/simplest programs that output that ...
- 441
5
votes
3
answers
283
views
Is there any other computation theory besides the one in automata theory?
I'm a bit confused at a fundamental level.
In Computer Science, maybe some of us mostly use discrete mathematics since our computer is digital (like during studying operating system, algorithms, ...
- 327
4
votes
1
answer
2k
views
Question regarding Cook-Levin theorem proof
I know a key part of the Cook-Levin theorem proof (as presented in the book by Sipser) is that given two rows of configurations, if the upper row is a valid configuration of a nondeterministic Turing ...
4
votes
2
answers
475
views
Cook-Levin theorem proof's requirement of $\phi_{cell}$
I'm trying to understand the Cook-Levin theorem proof, as it attempts to create a polynomial-time reduction from any NP problem to ...
- 41
3
votes
1
answer
122
views
Why isn't DIV necessarily in P? [duplicate]
In my formal languages class, we discussed DIV, defined as following:
$\mathrm{DIV} = \{\langle a,b\rangle : \text{$a, b \in N$ and $a$ has a divisor $d$ for some $1 < d \leq b$ }\}$
($\langle\...
- 33
3
votes
1
answer
741
views
What is the complexity of deciding if the intersection of a regular language and a context free language is empty?
Let's say we have a context free language, the CFG that produces it.
And then we have a DFA for a regular language.
If the intersection is empty is decidable, but how and how efficiently?
And if ...
- 217
3
votes
1
answer
85
views
Complexity of self-reducible set
I am trying to solve the following problem:
A set $S$ is self-reducible if the following holds: $x \in S$ iff $x = 1$(Base case) or (recursively) $l(x) \in S$ and $r(x) \in S$ where $\left|l(x)\...
- 213
3
votes
1
answer
885
views
How to apply "verification" and "decision" for the SUBSET SUM problem?
The SUBSET SUM problem states that:
Given finite set S of integers, is there a subset whose sum is exactly t?
Can someone show me why verification is simpler ...
- 821
3
votes
1
answer
116
views
$m/p$-equivalence holds after union with an arbitrary finite language
Problem 1: Let $A,B$ be languages over some alphabet $\Sigma$, if $A \equiv_m B$, then for every finite language $C$, $A \cup C \equiv_m B \cup C$.
Problem 2: Problem 1 but using polynomial time ...
- 133
3
votes
1
answer
122
views
grammatical complexity of propositional and monadic predicate validities? (and grammars for recursive but not context-sensitive languages?)
Consider two sets: the set of validities of propositional logic and the set of validities of monadic predicate logic. Call the first set $VP$ and the second set $VQM$. Both of these sets are decidable,...
- 131
3
votes
0
answers
183
views
Hopcroft & Ullman: 1969 vs. 1979
How do the 1969 and 1979 books by Hopcroft & Ullman compare? Was the 1969 book an earlier version of the 1979 book?
1969: Formal Languages and their Relation to Automata
1979: Introduction to ...
- 131
3
votes
0
answers
29
views
How to model grammar ambiguity
Say you have a (context-free) grammar, and you wish to mathematically model the magnitude of the ambiguity possible under this grammar, across the space of all possible** input strings.
Practically, ...
- 361
2
votes
1
answer
79
views
$\mathsf{RegExpEq_*} \in \mathsf{coNPC}$ but why isn't in $\mathsf{P}$
Hello for a homework I have to show that deciding whether a regex over $\Sigma = \{0,1\}$ descibes $\Sigma^*$ is $\mathsf{coNP}$ complete (this is irrelevant for the question though).
The thing which ...
- 23
2
votes
2
answers
46
views
P reduction between np-complete to np-complete
given 2 lagnauges A,B which are npc.
is there a reduction function from A to B $A \leq_PB$ ?
my idea was to say that since they are decideable,
we can do this:
$$
f(x) = \begin{cases} y \in B & \...
- 123
2
votes
2
answers
391
views
Complement of languages and coNP
By definition, any language (decision problem) $L$ is defined as a subset of $\{0,1\}^*$, where $\{0,1\}$ is the alphabet.
$L^c$ is said to be the complement of the language, and it seems to be ...
- 217
2
votes
1
answer
190
views
Is SAT a single language or a union of languages?
I know that a language is in NP if a Turing machine can decide the language of its checking relation $\{\text{boolean formula }\#\text{ truth assignment | truth assignment is correct}\}$ in polynomial ...
- 145
2
votes
1
answer
776
views
Are Context Sensitive Grammar with Polynomial Complexity Time?
Accordingly, to the question Chomsky Hierarchy and P vs NP, Context-Sensitive Grammars are on Linear Space.
Assuming a Deterministic Parser is the one which can parse unambiguous grammars in ...
- 215
2
votes
1
answer
144
views
Definition of complexity classes?
My book uses this definition for the Polynomial complexity class ($L$ is a language over $\{0,1\}$):
$$\mathrm{P} = \left\{L\subseteq\{0,1\}^*\;\middle|\; \begin{array}{l} \text{there exists an ...
- 23
2
votes
1
answer
103
views
Transitions of Turing machine in Cook Levin theorem proof
I am looking at the proof of the Cook-Levin theorem in Computers and Intractability: A Guide to the Theory of NP-Completeness. In particular, I find one thing ...
- 133
2
votes
2
answers
129
views
State whether the language is in $R$, $RE$, etc. The intuition for the solution
I saw the solution but can't understand the intuition of the following question:
Let's define
$$L^{\ge k} = \{w\in L : |w| \ge k\}$$
and
$$L=\{\langle M\rangle | \exists k:L(M)^{\ge k} = \overline{HP}^...
- 373
2
votes
1
answer
435
views
Is computing the cardinality of sum of regular expressions without kleene star closure EXPTIME problem?
Is computing the cardinality of sum of regular expressions without kleene star closure is EXPTIME problem?
Note that sum of regular expressions is union of regular expressions. The alphabet of each ...
2
votes
1
answer
3k
views
How to show that the complement of a language in $\mathsf P$ is also in $\mathsf P$? [duplicate]
If $L$ is a binary language (that is, $L \subseteq \Sigma = \{0,1\}^∗$) and $\overline{L}$ is the complement of $L$:
How can I show that if $L \in \mathsf P$, then $\overline{L} \in \mathsf P$ as ...
- 125
2
votes
1
answer
1k
views
Reduction function from A to its complement
I wanted to ask a simple question.
Lets say we have A, language of all the words with more then 3 letters. so it belongs to R.
and its complement , is the language of all words with less then 3 ...
- 133
2
votes
2
answers
446
views
Recursive definition of a language $ L $ over $ \{a,b\} $
How would I start the recursive definition of the following language:
L over {a, b} such that L consists of strings in which each
occurrence of b is immediately preceded and followed by an a
The '...
2
votes
1
answer
3k
views
If a language is m-reducible to a regular language, does it mean that this language is also necessarily a regular language?
I've been going back and forth with this for a dew days, can't quite be sure.
When I look at the pumping lemma method, I think a context-free language could possibly be reduced to a regular language....
- 23
2
votes
1
answer
1k
views
If A many-one reduces to B, does the complement of A many-one reduce to the complement of B?
If A many-one reduces to B, does the complement of A many-one reduce to the complement of B? My gut says no but I am having a hard time finding a counterexample.
- 21
2
votes
0
answers
51
views
How do I develop a structured work method for theoretical computer science? [closed]
Please excuse the soft question and please dont close it prematurely as too broad.
When working on assignments that includes a wide range of topics from theoretical computer science (see tags), I ...
- 377
1
vote
4
answers
3k
views
The language of TMs accepting some word starting with 101
I have a homework question about the properties (decidability, Turing-recognizability, etc.) of the language
$$ L = \{ \langle M \rangle | \text{$M$ is a TM and $M$ accepts some string $w$ which has ...
- 61
1
vote
1
answer
55
views
Is the difference between an unrecognizable language and a finite language decidable? recognizable?
Given 2 languages, A and B, such that A is not turing recognizable, B is finite, is it true that A-B is necessarily not turing recognizable?
I am studying to an exam and would appreciate your help! I ...
- 11
1
vote
2
answers
49
views
We cannot recognize a set of languages as the language themselves
"We cannot recognize a set of languages as the language themselves"
What is the meaning of the line and why we cannot do it and how is the encoding of TM is helping in that?
- 11
1
vote
1
answer
66
views
Is it true that PRIMES are in SPARSE?
I'm wondering if PRIMES, the language of all prime numbers represented in binary, which is $\{10, 11, 101, 111, 1011, 1101, ...\}$, belongs to the SPARSE class, a set of all sparse languages, that is, ...
- 127
1
vote
1
answer
558
views
Why every finite language is polynomial?
I understand that it's possible to build TM that check all the finite number of cases, so it's definitely in $R$, but I'm not sure why it's in $P$
- 373
1
vote
1
answer
39
views
More the number of for loops greater the problems solved
This is more a formal language theory question.
Imagine a setting where you are given a very basic programming language where variable assignments etc are taken care of without any of the iteration ...
- 83
1
vote
1
answer
93
views
Prove that $L = \{ xy \in \{a , b \}\textbf{*} \mid |x|_a = 2|y|_b \}$ is not regular
Prove that $L = \{ xy \in \{a,b\}^* \mid |x|_a = 2|y|_b
\}$ is not regular.
I have already tried to prove it by using the pumping lemma and reduction to absurdity, but have been unsuccesful on both. ...
- 11
1
vote
1
answer
119
views
Is Language $ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $ context free?
$ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $
I would use the Ogden pumping lemma. Assumption $n < m$ where $n$ is a number from lemma. My ...
- 53
1
vote
1
answer
194
views
Can quantum computer compute the minimal intersection DFA of numerous minimal DFAs in polynomial time using polynomial number of qubits?
Can quantum computer compute the minimal intersection DFA of numerous minimal DFAs in polynomial time using polynomial number of qubits, where the language of each given minimal DFA is finite and it's ...