Alex' Gardenアレックスの庭

Home

❯

5_Archive

❯

Other

❯

Uni

❯

Modules

❯

WS21 22

❯

NL1

❯

VL (1)

❯

VL04

❯

Non deterministic finite automata

1 min read

🔢 Non-deterministic finite automata

=== 🏁 Finite state automata with 0 or more transition functions in the same state for the same symbol (= multiple states at a time)==

Methods

  • 🔙 Backtracking

📖 Example:

  • Σ = {0,1}
  • F = {F0, F1}
graph LR
s0 --"0"--> s1
s0 --"0"--> s3
s0 --"1"--> s2
s1 --> qf0
s2 --"0"--> s3
s2 --"1"--> s4
s3 --> qf1

🔗 Links

1️⃣ Deterministic finite automata

Graph View

  • 🔢 Non-deterministic finite automata
  • Methods
  • 📖 Example:

Backlinks

  • NL1 Lectures
  • 1⃣ Deterministic finite automata
  • Backtracking
  • Finite state automata
  • ‍RegEx FSA implementation