# AUTOMATA

## Recommended Posts

WHAT IS POWER OF DETERMINISTIC AUTOMATA AND POWER OF NON-DETERMINISTIC AUTOMATA ?

##### Share on other sites

Deterministic Finite Automata can be reduced to canonical form . . . .

Nondeterministic Finite Automata can be in several states at once, is not limited to constant space, and is easier to formulate . . . . .

##### Share on other sites

• 2 weeks later...

Deterministic Finite Automata can be reduced to canonical form . . . .

Nondeterministic Finite Automata can be in several states at once, is not limited to constant space, and is easier to formulate . . . . .

Deterministic means that there is only 1 possible path to take, decision to take

Non-deterministic means there are more than 1 possible path to take, but Automata cannot be in more than 1 state at the same time, otherwise it's a Quantum Automata

##### Share on other sites

Deterministic means that there is only 1 possible path to take, decision to take

Non-deterministic means there are more than 1 possible path to take, but Automata cannot be in more than 1 state at the same time, otherwise it's a Quantum Automata

A "nondeterministic" finite automaton (NFA) has the power to be in several states at once." Introduction to Automata Theory, Languages, and Computation 2nd Ed. by John E. Hopcroft et. al.

The book further goes on to make sense of its statement!

Edited by Xittenn
##### Share on other sites

A "nondeterministic" finite automaton (NFA) has the power to be in several states at once." Introduction to Automata Theory, Languages, and Computation 2nd Ed. by John E. Hopcroft et. al.

The book further goes on to make sense of its statement!

I'll say the same thing .. Automata cannot be in more than 1 state at the same time,

The book used the phrase "to be in several states at once." which is disturbing to explain what "non-deterministic"

means, which meaning was explained in a better manner in my previous post

One example of a Non-deterministic Finite Automata (NFA) is Probabilistic Finite State Machine which can represent

the transition between states for a system, the system itself cannot be in more than one state at the same time,

otherwise it's quantum finite state machine, which represent the state transition tree that differs between the observer

and the real state since the last observation, check: DFA, NFA, Probabilistic Finite State Machine, Quantum Theory,

Reality Theory, Sound Theory

Note: I didn't say the book statement was wrong, I just stated something different than what you presented,

and [ 1 − 2 + 3 − 4 + · · · ] = [ Σ N - (N+1) ] = [ Σ -1 ] = $-\infty$

Edited by khaled
##### Share on other sites

I'll say the same thing .. Automata cannot be in more than 1 state at the same time,

The book used the phrase "to be in several states at once." which is disturbing to explain what "non-deterministic"

means, which meaning was explained in a better manner in my previous post

One example of a Non-deterministic Finite Automata (NFA) is Probabilistic Finite State Machine which can represent

the transition between states for a system, the system itself cannot be in more than one state at the same time,

otherwise it's quantum finite state machine, which represent the state transition tree that differs between the observer

and the real state since the last observation, check: DFA, NFA, Probabilistic Finite State Machine, Quantum Theory,

Reality Theory, Sound Theory

Note: I didn't say the book statement was wrong, I just stated something different than what you presented,

and [ 1 − 2 + 3 − 4 + · · · ] = [ Σ N - (N+1) ] = [ Σ -1 ] = $-\infty$

For starters the OP was a question with regards to the quality of each. I stated that the quality of a DFA is that it can be reduced to canonical form! This was not my attempt at describing what a DFA is considered to be, but what quality it possesses.

The statement the OP made about 'powers' was suggestive to me of his reading of this very title, and if this is the case, our personal opinions on the matter are fairly irrelevant. The books explanation of this is formal and sensible and I do not feel the need to justify what the book is trying to propose; it isn't really mine to be justifying anyway. The OP seemed to be concerned with homework and my original post was simply an attempt to either make obvious what the poster was already reviewing or to incite the OP to post a more detailed question.

If you wish to disagree with the literature I would ask you to give your reasoning behind your statements before I make arguments against your proposals and in favour of the aforementioned literature. You have clearly stated that NFA or Automata as a whole are not capable of being in several states at once and have gone so far as to call it disturbing, but you give no reason why. You make a rather vague statement with respect to implementers of such behaviour being 'quantum' but give no justification or explanation.

Forgive me here Khaled but your qualifications are not enough for me to take you at face value. Granted I am the least expert opinion, which is why I am formulating my opinions from literature and not from my own experience. I don't believe you have noted any objections to NFA being alleviated from the restriction of constant space, or my assertion that NFA are more easily formulated, so I will not address these points.

And also, my signature was simply a statement about my persons and my own qualities. The series is divergent, as am I

Edited by Xittenn
##### Share on other sites

Forgive me here Khaled but your qualifications are not enough for me to take you at face value. Granted I am the least expert opinion, which is why I am formulating my opinions from literature and not from my own experience. I don't believe you have noted any objections to NFA being alleviated from the restriction of constant space, or my assertion that NFA are more easily formulated, so I will not address these points.

I'd write things in logic, if they are easier to be understood: $\{ \; Human \;\; errs \;\; \rightarrow \;\; Author \;\; errs \;\; \rightarrow \;\; Book \;\; errs \; \}$,

my point was that not everyone can explain computational theories in a clear way ...

No need for apologize, you don't have to qualify me either .. I know this much, because I'm a researcher in computer science,

besides not only you formulate opinions from literature, how did I learn then .. and don't go far I wasn't speaking about the theory,

I was speaking about how proper should it be explained to students ...

thanks

Edited by khaled

## Create an account

Register a new account