Niedeterministyczny skończony automat jest skończonej maszyny stanów, gdy krotka jest mapowany do wielu stanach. To znaczy. zastępujemy zwykłą funkcję przejścia DFA inną funkcją .
Jeśli wiesz, czym jest NFA, możesz pominąć następną sekcję.
Definicja formalna
NFA jest jednoznacznie opisany przez
- skończony zbiór stanów
- skończony zestaw symboli
- funkcja przejścia
- stanie początkowym
- zbiór stanów końcowych
Maszyna rozpoczyna od i czyta skończony ciąg symboli , dla każdego symbolu jednocześnie zastosuje funkcję przejścia z aktualnym stanem i doda każdy nowy zestaw stanów do zbioru stanów bieżących.
Wyzwanie
Na to wyzwanie będziemy ignorować uproszczenie go, ponadto alfabet zawsze będzie (małymi literami) litery do Z oraz zbiór stanów będzie { 0 ... N } jakiegoś nieujemną liczbą całkowitą N . Stan początkowy zawsze będzie wynosił 0 .
Biorąc pod uwagę słowo i opis NFA, Twoim zadaniem jest określenie wszystkich stanów końcowych.
Przykład
Rozważ ciąg i następujący opis:
state, symbol, new-states
0, 'a', [1]
1, 'a', [0]
1, 'b', [1,2]
Maszyna uruchomi się w :
- przeczytaj : nowe stany { 1 }
- poczytać : nowe kraje { 1 , 2 }
- przeczytaj : nowe stany { 0 }
- przeczytaj : nowe stany { 1 }
- poczytać : nowe kraje { 1 , 2 }
Zatem stany końcowe, a tym samym wynik wyniósłby .
Uwaga: W kroku (2) przejście stanu odwzorowuje na ∅, ponieważ opis obejmuje tylko przejścia do niepustych zbiorów.
Zasady
Dane wejściowe będą składać się z łańcucha i pewnego rodzaju opisu NFA (bez -transitions):
- ciąg wejściowy zawsze będzie elementem
- prawidłowe dane wejściowe (nie ograniczone do):
- lista / tablica krotek / list
- wejście oddzielone nowym wierszem
- opis NFA będzie zawierał tylko przejścia z niepustymi zestawami
- możesz skracać reguły tymi samymi znakami, jeśli ich wynik jest taki sam (np. reguły
0,'a',[1,2]i0,'b',[1,2]można je skracać0,"ab",[1,2] - możesz wziąć każdą regułę osobno (np. reguła
0,'a',[1,2]może być0,'a',[1]i0,'a',[2])
- możesz skracać reguły tymi samymi znakami, jeśli ich wynik jest taki sam (np. reguły
- jeśli chcesz, możesz wybrać wielkie litery
- możesz przyjąć liczbę stanów jako dane wejściowe
- możesz założyć uporządkowanie wejść (np. uporządkowane według stanu lub symboli)
Dane wyjściowe będą oddzielonymi listami / zestawami / nowymi wierszami danymi wyjściowymi itd
- kolejność nie ma znaczenia
- bez duplikatów (ponieważ jest to zestaw)
Przypadki testowe
Te przykłady będą w formacie, w description word -> statesktórym descriptionznajduje się lista krotek (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]