Questions tagged [theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7
votes
3answers
717 views

Why does a DFA have multiple final states?

I am taking a course on programming language design and we got to the DFA part. It is known to be formally defined by a 5-tupple but they did not make it very clear to us why a DFA can have multiple ...
3
votes
4answers
160 views

Are all computer viruses man-made?

I'm curious if the origin of any successful computer virus is known to NOT have an intentional, human originator. To put it another way, do computer viruses ever "spontaneously" originate through the ...
0
votes
1answer
21 views

Mcculloch and Pitts Neurons: Is there errata in this article?

The paper A LOGICAL CALCULUS OF THE IDEAS IMMANENT IN NERVOUS ACTIVITY has the following description of neurons, which I question if there is errata or perhaps I need more information to understand ...
5
votes
1answer
53 views

Is there such a notion as “effectively computable reductions” or would this be not useful

Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by ...
1
vote
0answers
63 views

Chomsky Normal Form for context free grammars ambiguous/unambiguous properties?

My textbook states: Finally, it must be stressed that the Chomsky normal form says nothing about ambiguity in general—a CFG in Chomsky normal form may or may not be ambiguous, just like we have for ...
15
votes
2answers
5k views

Can a deterministic finite automaton ever go into an infinite loop?

As the title suggests, is this possible? Or does it halt execution when it hits the trap state? Thanks to anyone who can clear this up.
2
votes
1answer
41 views

NFA equality for automata with partial transition functions and all states accepting

Given two nondeterministic finite state automata with partial transition functions, such that all states are accepting, except for the implicit failure sink state, is it possible to decide in ...