All Questions
Tagged with complexity-theory formal-languages
100 questions
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
0
answers
16
views
Critical Pair Determination in Knuth Bendix
In the Knuth Bendix completion algorithm, how does one identify all the critical pairs for an abstract term rewriting system? Does one have to iterate through each rule, and then identify which pairs ...
- 11
-1
votes
1
answer
32
views
is my attempt correct? proof that L in P or in NPC? $L=\{G$ is an undirected graph on n vertices VC $U$ and an IS $I$ such that $|U|+|I|=n+10$ \}
I am facing a problem with the validity of the reduction function, may I get some assist in solving this issue, please?
$L=\{<G>| G$ is an undirected graph on n vertices that has a Vertex Cover $...
- 201
1
vote
1
answer
57
views
Communication complexity of Dyck language
I've been reading papers on streaming algorithms and ran across the following question which I haven't been able to answer: Consider the Dyck language $Dyck(2)$ over the alphabet $A = \{(,),[,]\}$ and ...
- 11
0
votes
0
answers
93
views
Efficient Algorithm To Find A Path Which Covers Maximum Area Along Polygonal Perimeter For Surveillance Application
In the context of surveillance, I am working on a project where the goal is to find an algorithm that determines a path along a polygonal area, connecting a root node to a target node, while ...
- 3
1
vote
0
answers
37
views
About infinite languages in RE and coRE
Let $L \in RE$. Then $L$ might be finite or infinite.
I assume this is also true for $coRE$.
But, if I have a language $L \notin RE$, it necessarily means that $L$ is infinite, am I correct?
Also, if $...
- 47
0
votes
0
answers
41
views
Complement of a language definition
Let $A=\{$ M is a TM, $s\in \mathbb{N}$ and $\exists x\in\Sigma^*$ s.t M rejects $x$ in at most $s$ steps $\}$.
I want to define its complement, so how do I negate "$\exists x\in\Sigma^*$ s.t M ...
- 47
1
vote
1
answer
70
views
What complexity class is this?
Disclaimer 1: I am a beginner in this domain and I am self-learning these concepts. Please take this in consideration when reading my question.
Disclaimer 2: All corrections to this question are ...
- 31
0
votes
1
answer
56
views
How to prove that a subset of a language L is related to NP while L is related to P?
a friend sent me a question where we're given language $L$ and its subset $E(L)$ such that:
$$E(L)=\{E(w)\ |\ w\in L\}\\\text{such that}\\
E(w)=\{w_{even}=\sigma_2\sigma_4\dots\ |\ w=\sigma_1\sigma_2\...
- 469
1
vote
0
answers
38
views
How to show a language is not recursive, without using reductions?
I would like to show a language is in not recursive (not in the family $R$) without using a reduction from a language that is known to be non-recursive. In other words, its as if I am discovering the ...
- 142
0
votes
0
answers
46
views
Lower bound for $a^kb^k$ in one-tape TM
For the language
$ L= \{a^kb^k | k \geq 0 \} $
How can i show there is no one-tape Turing Machine that can decide $L$ in less than $O(n\log n)$ time ?
- 368
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
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
0
votes
3
answers
435
views
How it's possible decide CNF by having a turing machine that decide SAT?
Suppose we have a Turing machine $M$ as black box that decide $SAT$ problem. Now suppse we have a $CNF$ formula $\phi$ with $n$ variables. How it possible checking satisfiblity of $\phi$ and then ...
- 323
1
vote
1
answer
346
views
If a TM accepts a non-regular language, its space complexity is $\Omega(\log \log n)$
I have been given an assignment that I'm having a very hard time understanding.
The assignment is to prove that if an algorithm accepts a non-regular language, the complexity is $\Omega(\log \log n)$ (...
- 13
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
1
vote
1
answer
93
views
The Turing Machine in the proof of Time Hierarchy Theorem
In the proof of the Time Hierarchy Theorem, Arora and Barak writes:
Consider the following Turing Machine $D$: “On input $x$, run for $|x|^{1.4}$ steps the Universal TM $U$ of Theorem 1.6 to simulate ...
- 13
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
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
0
votes
1
answer
107
views
Question about reduction Proof
I've recently seen a proof that the set of Turing machines $L = \{encode(M) |L(M) \text{is closed under reversal}\}$ is not decidable.
The proof used following idea:
Reduce from the $A_{TM}$ problem ...
- 1
-1
votes
1
answer
81
views
For every Non Deterministic polynomial Turing Machine $M$ exists $L(\overline{M})\in P \Leftrightarrow P=NP$
The $\Leftarrow$ direction is straightforward.
On the other hand for $\Rightarrow$ direction I have an idea of the prove but I don't sure about it.
For NTM, Non Deterministic Turing Machine, $M$, for ...
- 373
0
votes
1
answer
58
views
Is there a non-deterministic polynomial by time Turing machine such that: $L(M)\in NPC$ and $L(\overline{M})\in P$
When $\overline{M}$ is a non-deterministic polynomial by time Turing machine that final states switched: accept to reject and vice versa.
I'm thinking that this equal to $P=NP$, but I saw a solution (...
- 373
1
vote
1
answer
50
views
A question about domains in Karp reductions
A basic question or request for clarification regarding Karp reducibility:
Let $\Sigma^*$ be the set of all finite strings of 0's and 1's. Call a subset of $\Sigma^*$ a language. Let $\Pi$ denote ...
- 329
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
-3
votes
1
answer
48
views
Proof of existence of $L\in R\setminus P$
I saw some proof but I didn't understood it, any simple one?
- 373
0
votes
1
answer
263
views
Complementary for $SAT$
I have tried to find a definition of complementary language to $SAT$, I mean $\overline{SAT}$.
But I still confused, in case of $L\in \overline{SAT}$ is it mean:
if $\varphi\in L$ then all ...
- 373
-1
votes
2
answers
77
views
Recursively enumerable notation $RE$ vs. $RE\setminus R$
I know that it's a bit stupid question.. , but still,
Is there any difference between $RE$ and $RE\setminus R$ notations?
I'm asking because I saw that in some places using both of the notations, for ...
- 373
0
votes
1
answer
42
views
For s set $S\subseteq RE$, so call feature of language $S=\emptyset$ vs. $S=\{\emptyset\}$
I'm trying to understand what's the difference between $S=\emptyset$ and $S=\{\emptyset\}$
The diffenition that I found for $L_S=\{\langle M\rangle\ | L(M)\in S \}$
I understood that $S=\emptyset$ and ...
- 373
0
votes
1
answer
55
views
Is a language recursive? 2 wrong ways of solving
Let's define:
$Disagree(M_1,M_2) = \{x| $The result of $M_1$ on $x$ different from the result of $M_2$ on $x\}$
that means: if $M_1$ accept, $M_2$ reject and vice versa
$NPA=\{L|\exists M_1,M_2$ ...
- 373
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
1
vote
1
answer
207
views
Finite languages $L\in RE$
I want to check if I understood it in the right way.
In some example where $L\in RE$ the explanation deal with 2 cases: 1st when $L$ finite and 2nd when $L$ infinite. In the second case $L\in R$, isn'...
- 373
1
vote
2
answers
64
views
Can you say anything interesting about a language knowing only that it is prefix-closed?
Suppose $L$ is an arbitrary formal language over a finite alphabet $A$, and suppose that $L$ is closed under prefixes (i.e. if $w \in L$, and $u$ is any prefix of $w$, then $u \in L$).
Knowing only ...
0
votes
1
answer
63
views
For an NFA, can we always find a RAM?
For an NFA, can we always find a RAM, which recognises the same language?
- 167
0
votes
1
answer
60
views
Is there a way to map the concatenation operation over strings to the addition operation over $\mathbb{N}$
Given an alphabet, say $\Sigma = \{0,1\}$, I can make a one-to-one mapping from all possible strings $x \in \Sigma^*$ to $\mathbb{N}$. This could be done by ordering $\Sigma^*$ lexicographically and ...
- 481
1
vote
1
answer
246
views
Formal defintion of SET-PARTITION as a language
I am not quite sure howto define SET-PARTITION as a language as in Sipser. Is it
$$
\left\{ \langle S,A,B\rangle \;\middle|\; (A,B) \text{ is partition of } S \text{ and } \sum_{n\in A} n = \sum_{n\...
- 160
1
vote
1
answer
46
views
Languages A, B ∈ NP-complete such that A⋃B = Σ*
I'm pretty new to complexity theory and it seems like I stuck with this problem. We should find language $B$ such that it accepts any words rejected by $A$ but in that case, it seems that $B$ is a ...
- 13
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
0
votes
0
answers
205
views
how to write a language for context-free grammar generates the empty string?
How would you write a language for a context-free grammar that generates an empty string. Is it something like E = { (G) | G is a CFG and L(G) = Ø}?
1
vote
1
answer
70
views
Arithmetical Hierarchy, show $\Sigma_1$ is Turing recognizable
I'm new learning Arithmetical Hierarchy, my question ask to show that $\Sigma_1$ is Turing recognizable.
I'm not sure what's the general way to approach this, but I noticed $A_{TM}$ is in $\Sigma_1$ ...
- 371
0
votes
0
answers
58
views
One-way-function based on Friedberg numberings
A one-way-function is an easy to compute function $y=f(x)$ which is hard to invert. In 2000 Levin showed an example of a function which is one-way if there are one-way functions. As far as I know, it ...
- 109
0
votes
1
answer
116
views
How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$
Create an CFG for all strings over {0, 1} that have the an even number of 0’s and an odd number of 1’s.
Also, I have a hint
HINT: It may be easier to come up with 4 CFGs – even 0’s, even 1’s, odd 0’s ...
- 11
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
-3
votes
1
answer
65
views
I want to solve this question for algorithm, please [closed]
Write an algorithm that calculates the monthly payment of a bank loan with
a fixed interest-rate. Given the principal amount, the fixed interest rate, the number of
years to pay the loan, you can ...
- 3
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
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
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
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
0
answers
138
views
Proving existence of a language $L\in DTIME(n^{\log n})$ which is not in $Avg-P$
I'm struggling with the following question:
Define $Avg-P$ the class of all languages $L$ for which there exists a polynomial time Turing Machine $M$ such that for every $n$, for all but $\frac{2^n}{...
- 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
3
answers
320
views
how can i say a given problem is in co-NP using it's definition?
I seem to be having trouble understanding the connection between the formal definition of co-NP and how problems are concluded to be in it. co-NP is defined to be the class containing the languages ...
user92484