Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.3k answers

1.7k comments

557 users

0 votes
If the exam question for example states  "Create an automat which accepts different sequences (e.g. aa,aabbaa,...) but doesn't accept alone standing a's or b's", does it matter if we model a deterministic or non-deterministic automat?

Is ending in a wrong state (not a final state) equivalent to reading letter σi in state si where no si+1 for this letter exists?
in * Other Teaching Fields by (200 points)

1 Answer

+2 votes

does it matter if we model a deterministic or non-deterministic automat

Any exercise will state whether you should build a deterministic or non-deterministic automaton. If not, please ask and we will clarify this in the exam on the blackboard.


Is ending in a wrong state (not a final state) equivalent to reading letter σi in state si where no si+1 for this letter exists?

No that are two different things: If a deterministic automaton is not in a final state after reading an input sequence, it simply means, that the input was "not accepted". That is a valid computation, since the automaton's job is to tell us whether an input sequence is accepted or not (is part of the described language or not). That is different from having no successor state. If there is no successor state (e.g. you read 'a', but there is no outgoing transition with 'a') then this is not a valid computation.

In deterministic automata this can't happen, since we must have exactly one outgoing transition for each symbol, for each state (take a look at the transition function \delta).

In non-deterministic automata this is ok, since the transition function \delta maps to a set of possible successors (which can be the empty set), and acceptance is defined via "exists a path ... " rather than one path.

by (2.4k points)
Thank you for your quick response.

"In non-deterministic automata this is ok, since the transition function \delta maps to a set of possible successors (which can be the empty set), and acceptance is defined via "exists a path ... " rather than one path."

So if we end up in an empty set (in a non-determistic automat), would it be valid but not accepted?
You don't "end up in an empty set". The definition is "if there exists a path from any initial state to a final state with the given input sequence, then the input sequence is accepted". So if it is not possible to reach a final state with the input, then the input is not accepted. But if it is possible to reach a final state with the input, then it is accepted.

Related questions

0 votes
1 answer
asked Aug 22, 2020 in * Other Teaching Fields by davidschulz (410 points)
0 votes
1 answer
asked Aug 21, 2020 in * Other Teaching Fields by Eichi (200 points)
+1 vote
1 answer
asked Aug 18, 2020 in * Other Teaching Fields by davidschulz (410 points)
+1 vote
1 answer
asked Aug 18, 2020 in * Other Teaching Fields by Eichi (200 points)
0 votes
1 answer
asked Aug 18, 2020 in * Other Teaching Fields by davidschulz (410 points)
Imprint | Privacy Policy
...