Automata & Formal Languages Lab
Write regex patterns and see matches highlighted in test strings. Build deterministic finite automata and step through state transitions symbol by symbol. Compare regex and DFA representations of the same language.
Guided Experiment: Building a DFA for Divisibility
Can a finite state machine with only 3 states correctly determine whether any binary number is divisible by 3? How do the states track the remainder?
Write your hypothesis in the Lab Report panel, then click Next.
Controls
Regex Results
Data Table
(0 rows)| # | Input | Pattern / FSM | Matches / Accepted | Details | Type |
|---|
Reference Guide
Regular Expressions
Regular expressions define patterns for matching strings. They use character classes, quantifiers, and grouping.
Common elements include . (any character), * (zero or more), + (one or more), ? (optional), and character classes like [0-9].
Finite State Machines
A DFA (deterministic finite automaton) is defined by states, transitions, a start state, and accept states.
For each state and input symbol, there is exactly one transition. A string is accepted if the DFA ends in an accept state.
Regex-DFA Equivalence
Every regular expression has an equivalent DFA, and vice versa. They describe exactly the same class of languages, called regular languages.
However, some languages (like balanced parentheses) cannot be expressed by either, requiring more powerful tools like pushdown automata.
The Chomsky Hierarchy
Languages are classified by the computational power needed to recognize them.
Regular languages (DFA/regex) are the simplest. Context-free languages (parsed by PDAs) include most programming languages.