15
4
A nondeterministic finite automaton is a finite state machine where a tuple \$(state,symbol)\$ is mapped to multiple states. Ie. we replace the usual \$\delta : Q \times \Sigma \to Q\ \$ transition function of a DFA with another function \$\Delta : Q \times \Sigma \to \mathcal{P}(Q)\$.
If you know what an NFA is you might want to skip the next section.
Formal Definition
An NFA is uniquely described by
- \$Q\$ a finite set of states
- \$\Sigma\$ a finite set of symbols
- \$\Delta : Q \times \Sigma \to \mathcal{P}(Q)\$ the transition function
- \$q_0 \in Q\$ the initial state
- \$F \subseteq Q\$ a set of final states
The machine starts out in \$q_0\$ and reads a finite string of symbols \$w \in \Sigma^*\$, for each symbol it will simultaneously apply the transition function function with a current state and add each new set of states to the set of current states.
Challenge
For this challenge we will ignore \$F\ \$ to simplify it, furthermore the alphabet will always be the (lower-case) letters \$\texttt{a}\ \$ to \$\texttt{z}\ \$ and the set of states will be \$\{0 \dots N\}\$ for some non-negative integer \$N\$. The initial state will always be \$0\$.
Given a word \$w \in \{\texttt{a}\dots\texttt{z}\}^*\$ and a description of the NFA, your task is to determine all the final states.
Example
Consider the string \$\texttt{abaab}\$ and the following description:
state, symbol, new-states
0, 'a', [1]
1, 'a', [0]
1, 'b', [1,2]
The machine will start in \$q_0 = 0\$:
- read an \$\texttt{a}\$: new states \$\{1\}\$
- read a \$\texttt{b}\$: new states \$\{1,2\}\$
- read an \$\texttt{a}\$: new states \$\{0\}\$
- read an \$\texttt{a}\$: new states \$\{1\}\$
- read a \$\texttt{b}\$: new states \$\{1,2\}\$
So the final states and thus the output would be \$\{1,2\}\$.
Note: In step (2) the transition of state \$2\$ maps to \$\emptyset\$ as the description only includes transitions to non-empty sets.
Rules
The input will consist of a string and some kind of description of the NFA (without \$\epsilon\$-transitions):
- the input string will always be element of \$\{\texttt{a}\dots\texttt{z}\}^*\$
- valid inputs (not limited to):
- list/array of tuples/lists
- new-line separated input
- the description of the NFA will only contain transitions with non-empty sets as result
- you may abbreviate rules with the same characters if their result is the same (eg. rules
0,'a',[1,2]and0,'b',[1,2]could be abbreviated with0,"ab",[1,2] - you may take each rule separate (eg. rule
0,'a',[1,2]can be0,'a',[1]and0,'a',[2])
- you may abbreviate rules with the same characters if their result is the same (eg. rules
- you may choose upper-case letters if you want
- you may take the number of states as input
- you may assume some kind of ordering of the inputs (eg. ordered by state or symbols)
The output will be a list/set/new-line separated output etc. of the final states
- order doesn't matter
- no duplicates (as it's a set)
Test cases
These examples will be in the format description word -> states where description is a list of tuples (state,symbol,new-states):
[] "x" -> []
[] "" -> [0]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])] "abaab" -> [1,2]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])] "abc" -> []
[(0,'p',[0,1]),(0,'g',[2]),(1,'c',[1]),(1,'g',[4]),(1,'p',[2]),(2,'c',[0])] "ppcg" -> [2,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "foobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "fooooooobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "fobarfo" -> [1,2]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])] "foobarrf" -> [1]
[(0,'d',[1,2]),(1,'u',[2]),(2,'u',[2,3]),(2,'p',[3]),(3,'p',[3])] "dup" -> [3]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])] "aab" -> [3,1,4]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])] "abb" -> [1,2]
ბიმო
Posted 2018-09-04T16:22:57.123
Reputation: 15 345
related – ბიმო – 2018-09-04T16:25:05.980
3This brings back scary memories from my automaton course. – Don Thousand – 2018-09-04T16:29:10.680
Can we take input with individual lines for each new state, e.g. this for worked example?
– ovs – 2018-09-04T16:43:06.790@ovs: Sure go ahead! – ბიმო – 2018-09-04T16:53:32.487