cj gs

This hole is experimental, passing requirements may change. Solutions won't contribute to scoring until the hole goes live.

Please leave feedback on the GitHub issue.

Details

A nondeterministic finite automaton or NFA is a finite-state machine that may nondeterministically move to any of a set of states as it reads characters from a string.

Each input consists of a table describing the NFA, and a quoted input string, like so:

    | a | b | c |
→ 0 |{0}|{0}|{0,1}|
  1 |{2}| ∅ | ∅ |
  2 | ∅ |{3}| ∅ |
 F3 | ∅ | ∅ | ∅ |
acbcab

In this table, we can find the following information:

  • There are four states, called 0, 1, 2, and 3.
    • States are always digits 0-9. There may be up to 10 states.
  • There are three characters in the input alphabet: a, b, and c.
    • Input characters may be lowercase letters a-z or digits 0-9.
  • The table entries describe the set of states the NFA may transition to for each (current state, character) pair.
    • For example, if the current state is 0, and a c is read, the set of possible next states is {0,1}.
  • The row describing state 0 is marked with so it is the initial state. There is exactly one initial state.
  • The row describing state 3 is marked with F so it is an accept state. There may be multiple accept states, or none at all.

Use the table to move the NFA between sets of valid states by feeding it characters from the input string. Once the set of possible states is the empty set, it remains so.

In our example:

  • The initial state is 0. The first character is a. Looking at the table, we see the new set of possible states is {0}, so the NFA must be in state 0.
  • The current state is 0. The next character is c. Looking at the table, we see that the set of possible next states is {0,1}. Thus, the NFA may nondeterministically move to either 0 or 1. Or, alternatively, its set of possible locations is {0,1}.
  • The current state is either 0 or 1. The next character is b. Looking at the table, we see that if the state had been 0, it can be 0 next, while if it had been 1, it has no next state -- and that computation path dies. Thus, the set of reachable states after seeing substring acb is {0,1}.

Finally, print on separate lines the set of reachable states after processing the entirety of each input string, followed by a space, followed by either Accept (if the NFA can reach any accept state by processing the string, or, in other words, if the final set of valid states contains an accept state) or Accept (otherwise). In this case, we may end at either 0 or 3 and one of them is an accept state (3), so we print {0,3} Accept.

There may be multiple input strings presented on separate lines; print their respective outputs on separate lines. When printing a set, sort its elements numerically and use to denote the empty set. The empty string in the input is denoted by ε.

External links: Wikipedia

0 bytes, 0 chars
Restore solution
All
Compiled from AT&T syntax to x86-64 Linux. Use syscalls to write output.
05AB1E is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
ALGOL 68 is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
APL is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Arturo is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Befunge is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
BQN is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
CJam is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
CoffeeScript is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Egel is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Fennel is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Gleam is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Groovy is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Harbour is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Hare is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Haxe is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Hush is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Hy is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Odin is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Racket is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Rebol is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Rexx is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Scala is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Squirrel is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
Uiua is an experimental language, no solutions will be saved. Please leave feedback on the GitHub issue.
ctrl + enter or

Delete Solution

Are you sure you want to delete your solution(s) for NFA Simulator?

If you have separate bytes and chars solutions then both will be deleted.

This is irreversible, please backup any code you care about.

Type I understand and press confirm to continue.