Questions about automata, formal grammars or other computation-models that specifically relate to the use of nondeterminism. Not to be confused with randomness or ambiguity!
0
votes
1answer
21 views
Given a NP Algorithm for SAT, do we expect to have Correct and Incorrect Solutions?
I am reading about Boolean Satisfiability Problem and Nondeterministic Algorithms, in the latter defination it says :
In computational complexity theory, nondeterministic algorithms are ones that, ...
1
vote
0answers
17 views
What is the difference between the choice operator and nondeterminism in CSP?
I'm learning CSP now for my research. First time doing formal work in CS. I'm having a hard time understanding the difference between choice $\square$ operator and the nondeterminism $\sqcap$ operator....
2
votes
2answers
173 views
Why SAT Requires A Non-determinstic Algorithm?
I am getting started to understand the probelm of Satisfiability and i am reading (Computers and Intractability: A Guide to the Theory of NP-Completeness).
I do understand the difference between a ...
1
vote
1answer
32 views
How to implement a maximal munch lexical analyzer by simulating NFA or running DFA?
I'm planning to implement a lexical analyzer by either simulating NFA or running DFA using the input text. The trouble is, the input may arrive in small chunks and the memory may not be enough to hold ...
1
vote
2answers
41 views
Understanding $\epsilon$ transitions on NFA
I can't understand why $\epsilon$ is accepted. I thought if $\epsilon$ is inputed then it would go from $q_1$ to $q_3$. $a$ is also accepted, but I though if $a$ is inputed then then the NFA would die,...
4
votes
1answer
59 views
How do non-deterministic algorithms work on current machines?
I have some questions regarding the exact nature of non-deterministic algorithms. Is it right that non-deterministic algorithms do not rely on any randomness whatsoever? In which case, this Wikipedia ...
2
votes
1answer
32 views
In certificate view of NL can we force the guesses to be in some format like $a^n b^n c^n d^n$?
In certificate view of NL the size of our guess can be polynomial.Can this guesses be like $a^n b^n c^n d^n$. Can we force the guesses to be in some format? I think it(the format) can be in regex ...
0
votes
1answer
46 views
Drawing a NFA for a string
I have these grammar rules defined as follows,
FDL -> FDEF FDL | ε
FDEF -> #feature #: FEXP
FEXP -> #op #( FLIST #)
FLIST -> FEXP #, FEXP | #feature
...
1
vote
1answer
16 views
Can we call deterministic equivalent of all NFA to be finite
Finite automata is defined as a simple machine having small memory. A deterministic equivalent of a NFA with n states will have O(2^n) states,so the number of states grow exponentially. So can we ...
1
vote
1answer
24 views
What will happen if input is larger than required in a NFA
This is my first time in the field of TOC so I am not able to provide any self-approach while asking .In the above example what will happen if input string is "1001" or "1111"?The state q4 can be ...
1
vote
2answers
36 views
NP Class Definition of a Certificate
Given the definition for all x ∈ Σ∗
x ∈ L ⇔ ∃ u ∈ Σ∗ with |u| ≤ p(|x|) and M(x, u) = 1
Lets say the input x = ababab
Then the certificate u shouldn't be longer than p(|x|).
But what would be p(|...
3
votes
0answers
31 views
How to prove existence of the language
Consider such question:
(Prove or disprove) There exists a language in $TIME(2^{n^2})$ that is not in $NTIME(n)$.
I guess that answer is yes because $TIME(2^{n^2})$ and $NTIME(n)$ are totally ...
0
votes
1answer
46 views
Are there any estimated, imperfect or fuzzy sorting algorithms?
I'm implementing some estimation metrics that take samples of optimisation functions and estimate their properties. One of the metrics requires the data to be sorted; however, since the metric is only ...
2
votes
1answer
53 views
Can an algorithm be truly non-deterministic?
I read the term "non-deterministic algorithm" in many places but I don't see how an algorithm can be truly non-deterministic. Typically, there is some source of randomness in these algorithms. If the ...
2
votes
1answer
451 views
Understanding trap and dead state in automata
Well, this sounds somewhat basic definitions, but I feel they needs to be clearly defined.
In book by Hopcroft et. al., there is an excerpt:
...a dead state, that is, a nonaccepting state that ...
1
vote
2answers
58 views
Number of states in NFA and DFA accepting strings from length 0 to n with alphabet Σ= {0,1}
The question is in title. Let me repeat:
What are the number of states in NFA and DFA accepting strings from length 0 to n with alphabet $\Sigma = {0,1}$
I feel both NFA and DFA will take ...
0
votes
0answers
13 views
Is $NAAL_{NFA}\in\Bbb{P}$?
$NAAL_{NFA}=\{(a,n)|\;a\text{ is an encoding of a non-deterministic finite automaton without }\epsilon-\text{transitions, }n\text{ is a non-negative integer and }\exists w\in\Sigma^n:\;a\text{ rejects ...
0
votes
1answer
45 views
Is this language NP Hard?
$L=\{$$($$m$,$w$,$n$$)$| $m$ is an encoding of a non-deterministic Turing machine, $w$ is any word/string in the closure of alphabet, i.e. $w\in\Sigma^*$, $n$ is any positive integer, i.e. $n\in\Bbb{Z}...
0
votes
0answers
59 views
Where is proof that palindrom language is nondeterministic? [duplicate]
It is well-known that the language over $T$ with at least 2 symbols is nondeterministic. for simplicity, the language $\{ww^R: w\in\{a,b\}\}$ (even-length palindroms of $a$, $b$) is context-free, but ...
1
vote
2answers
46 views
Do NFAs with $\varepsilon$-moves never terminate?
Suppose in an NFA we have an $\varepsilon$-move from a state $q_0$ to $q_1$. According to Sipser,
Without reading any input, the machine splits into multiple copies one following each of the ...
1
vote
1answer
40 views
Questions on Sipser's NP implying verifiability?
I've revisited trying to understand the proof to why NTM exists iff there is a verifier. I think I'm finally understanding the proof but I want to make sure and thus have some questions as follow up ...
0
votes
1answer
27 views
NFA accepting $L=\{wbbav \;|\; w \in \{a,b\}^*, v \in \{a,b\}^+, v\; has\; suffix\; a\}$
I have to construct NFA that accepts language $L=\{wbbav \;|\; w \in \{a,b\}^*, v \in \{a,b\}^+, v\; has\; suffix\; a\}$.
My solution is this automata:
Can you tell me, if this is correct or not? If ...
0
votes
1answer
148 views
Is every decidable language a deterministic context free language?
I'm trying to get a better understanding for the relationship between decidability and a few other things so that I can get a better grasp of the topic. Any info helps!
Is every decidable language a ...
1
vote
3answers
99 views
Is there a method to compress all data without loss (lossless compression)?
I know that the answer is no but I'm not sure why. Here's where I started. We know that all data with length $n$ Bits and minimum $1$ Bit can be compressed, either lossless or lossy. But how do I ...
0
votes
0answers
64 views
show doubly connected graph is NL complete
The question:A directed graph is doubly connected if every two vertices are connected by a directed path in each direction. Let DCG = {| G is a doubly connected graph} Prove that DCG is NL-complete. (...
5
votes
0answers
101 views
Implications of $NL=P$
What would be some implications of $NL$$=P$? Would it be possible to get recommendations on good sources/papers I can read to learn more about this? Thank you
4
votes
1answer
81 views
Prove: if $\delta_D(q0, w) = p$ then $\delta_N(q0, w) = {p}$
In my textbook, it presents the theorem, "A language L is accepted by some DFA if and only if l is accepted by some NFA". My textbook explains that the "if" portion of the proof is given by the subset ...
1
vote
3answers
135 views
Minimal DFA with more states than its equivalent NFA
I understand that using a bad case for subset construction as provided through an example in the book - Introduction to Automata Theory, Languages and Computation, we can definitely have an NFA with $...
4
votes
1answer
64 views
Complement of Mealy machine
How could one reasonably define and construct the complement of a deterministic Mealy machine?
My intuition is that the complement should give exactly the opposite of output strings after a specific ...
0
votes
1answer
60 views
Constructing an FSA, where Ratio of number of states of FSA to its Minimal DFA Equivalent < 0.5
I need to choose a language, design a finite automaton M such that L = L(M). Construct a minimum-state DFA M′ equivalent to M in such a way that the ratio of the number of states in M to the number of ...
2
votes
1answer
73 views
Why nondeterminism?
Theory of computation often involves nondeterministic models of computation. Some examples include nondeterministic finite automata (NFAs), nondeterministic pushdown automata (PDAs), and ...
1
vote
4answers
130 views
How do NFA's make program design any better when converted DFA form can't remember original states?
Here is some content from the book by Peter-Linz I read
"Consider a game-playing program where the machine needs to make the decision for the next move [say for tic-tac-toe]. Since there are ...
2
votes
0answers
80 views
Simulating QC using nondeterministic Turing machine
Is it more efficient to simulate Quantum Computer using a non-deterministic Turing machine?
Would it be more efficient than simulation using a deterministic Turing machine or probabilistic Turing ...
0
votes
1answer
61 views
Confused b/w non-deterministic finite state automata vs finite state automata
I am reading this example of FSA from book Martin & Jurafsky "Speech and Language Processing".
As per definition of FSA you can only transition to one state after consuming one input. In this ...
0
votes
1answer
32 views
If all computations of non deterministic Turing machine on the input string are all accept then is the boolean formula of them a tautology?
If M is non deterministic Turing machine and w is any string then $\Phi_{M,w}$ is satisfiable if and only if M accepts w according to Cook and Levin (1971).
By the definition of non deterministic ...
0
votes
0answers
22 views
Is the boolean formula generated from the Cook's reduction necessarily in conjunctive normal form?
$\Phi_{M,w}$ is satisfiable boolean formula if and only if $M$ is non deterministic Turing machine that accepts string $w$ within $p(n)$ steps where $n=|w|$.
Cook showed in 1971 that deterministic ...
0
votes
0answers
36 views
How about boolean formula that is satisfied on every reject path and falsified on every accept path of non deterministic Turing machine? [duplicate]
Cook-Levin reduction is both deterministic polynomial time and parsimonious and that's mean that from every non deterministic Turing machine $M$ and string $w$ it is possible in polynomial time ...
-1
votes
1answer
65 views
Relating accepting/rejecting paths to satisfying/falsifying assignments in (Cook, 1971)
I read The Complexity of Theorem-Proving Procedures by Stephen A. Cook (1971).
Cook explains how to create a boolean formula $\Phi$ from $(M,w)$, where $M$ is a non-deterministic Turing machine that ...
1
vote
1answer
48 views
NP and verifiability equivalence - does this guarantee that any certificate can be verified in polynomial time?
As a follow-up from my old question here, I'm wondering more about the equivalence proof. Intuitively, NP has been described as the class of all problems which a solution certificate can be verified ...
0
votes
2answers
45 views
Does polynomial time reduction from CNFFAL to CNFSAT is also polynomial time reduction from CNFSAT to CNFFAL?
CNFSAT is the language of all strings that are encoding of satisfiable boolean formula in conjunctive normal form while CNFFAL is the language of all strings that are encoding of falsifiable boolean ...
1
vote
0answers
136 views
Converting a non-deterministic context free grammar to deterministic
I have the non-deterministic context free grammar $$I \to abcX | abdY$$
$$X \to X d | \epsilon$$ $$Y \to XX |I$$ and i want to convert it into a deterministic. I know that the rules $I \to abcX | abdY$...
1
vote
0answers
185 views
Comparing non-deterministic and also the deterministic expressive power of FA, PDA's and TM'S
I am sorta confused and also could not find a answer online, but in terms of expressive power, .
Non-deterministic FA, PDA, TM
NFA < NPDA < NTM
...
3
votes
1answer
66 views
On $NP=\Sigma_2^P$ from non-deterministic time?
We know $NP=\bigcup_{k\in\Bbb N}NTIME(n^k)$ and $\Sigma_2^P=NP^{NP}$.
Does $\Sigma_2^P\subseteq\bigcup_{k\in\Bbb N}NTIME(n^k)$ also hold (we can do $O(n^k)$ queries to $NP$ oracle which runs in non-...
3
votes
3answers
262 views
What is difference between nondeterministic polynomial time and exponential time?
I am not very into computer science theory but i feel like people are defining nondeterministic polynomial time as if it is another name of exponential time. I would be happy if you clarify it. thank ...
1
vote
1answer
34 views
Are probabilisitc algorithms deterministic?
I got confused with deterministic and probabilistic algorithms. Am I right by assuming that algorithms are called probabilistic once they use some sort of randomness?
Initially, I thought only ...
0
votes
1answer
63 views
On $UP$, $NP$, $\oplus P$ and $PP$?
We know $UP\subseteq NP\subseteq PP$.
Is $UP^{\oplus P}\subseteq NP^{\oplus P}\subseteq PP^{\oplus P}$?
I think the first $UP^{\oplus P}\subseteq NP^{\oplus P}$ is straightforward since whatever ...
0
votes
1answer
41 views
Closure of a CFL under specific operation
Consider the following operation on language $L$:
$\mathrm{inv}(L) = \{ xy^Rz \mid x,y,z\in \Sigma^*, xyz\in L \}$
I understand that if $L$ is regular, then $\mathrm{inv}(L)$ is regular too, and ...
2
votes
1answer
43 views
Finding non-trivial NFA that accepts all short strings
It is well-known that every non-trivial NFA of $k$ states (an NFA that does not accept all strings) rejects a string of length at most $2^k$.
But is this upper bound asymptotically tight ?
I found ...
0
votes
0answers
21 views
Non-deterministic limited Turing Machine that recognize the language $P$ of palindromes [duplicate]
After reading the following topics
Non-deterministic 2-tape Turing Machine that recognizes palindromes in linear time
Non-deterministic Turing machine and palindromes
I can't figure it out how to ...
0
votes
1answer
68 views
$U = \{ \langle M, x, \#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\}$ is NP complete
I'm trying to prove $U = \{ \langle M, x, \#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\}$ is NP-complete. Showing it is NP is trivial. NP-hardness is the hard ...
