Test 1 (Part 1): Regular Languages & Finite Automata Flashcards

Front

Definitions

Back

Key terms include alphabet $\Sigma$, string, empty string $\epsilon$, language, and acceptance. Know formal meanings and how these fit into automata definitions. Be able to apply each definition when proving properties or constructing machines.

Front

Finite Automaton

Back

A finite automaton is a 5-tuple $(Q,\Sigma,\delta,q_0,F)$ that reads input symbols and changes states according to $\delta$. It accepts a string if a computation ends in a state in $F$. Finite automata have finite memory and recognize regular languages.

Front

Deterministic FA

Back

A deterministic finite automaton (DFA) has a transition function $\delta$ that gives exactly one next state for each state and input symbol. There are no $\epsilon$-moves and for every state-symbol pair a defined transition exists (often made total). DFAs decide membership in linear time by single-path simulation.

Front

Nondeterministic FA

Back

A nondeterministic finite automaton (NFA) allows multiple possible next states for a state and input symbol and may include $\epsilon$-transitions. An NFA accepts a string if at least one computation path leads to an accept state. NFAs are equivalent in power to DFAs even though they may be more succinct.

Front

Regular Language

Back

A regular language is any language that can be recognized by some finite automaton (DFA or NFA) or described by a regular expression. Regular languages are closed under a variety of operations and have decidable properties. Many simple pattern-like languages over $\Sigma$ are regular.

Front

Regular Expression

Back

A regular expression is a formal notation using union, concatenation, and Kleene star to describe a set of strings over $\Sigma$. Every regular expression denotes a regular language and conversely every regular language has a regular expression. Regular expressions are used to specify pattern languages compactly.

Front

Equivalence (FA)

Back

Two finite automata are equivalent if they accept exactly the same language. Equivalence can be tested by constructing a product automaton to check if their symmetric difference is empty or by minimizing and comparing canonical DFA forms. Proving equivalence often uses structural conversions and language equality arguments.

Front

DFA–NFA Equivalence

Back

DFAs and NFAs recognize the same class of languages: the regular languages. The subset construction (powerset construction) converts any NFA into an equivalent DFA by making DFA states correspond to sets of NFA states. This theorem shows nondeterminism adds convenience but not expressive power.

Front

Regex–Language Equivalence

Back

Kleene’s theorem states that the class of languages described by regular expressions is exactly the class of languages recognized by finite automata. Constructions exist both ways: Thompson’s construction builds an NFA from a regex and state-elimination or generalized transition graphs yield a regex from an FA. This equivalence links algebraic and automata perspectives.

Front

Closure Properties

Back

Regular languages are closed under union ($\cup$), concatenation, Kleene star ($L^*$), intersection ($\cap$), and complement. Closure means applying these operations to regular languages yields a regular language. Knowing constructions for each closure is important for building or proving regularity.

Front

Union Construction

Back

For union of two automata you can make an NFA with a new start state and $\epsilon$-transitions to each machine’s start, or for DFAs use a product construction marking states where either component is accepting. The NFA method is simple and preserves compactness, while the DFA product produces a deterministic recognizer. Both implement $L_1\cup L_2$.

Front

Concatenation Construction

Back

To recognize concatenation $L_1L_2$ with automata, connect accepting states of the machine for $L_1$ to the start of the machine for $L_2$ using $\epsilon$-transitions in an NFA construction. The combined machine accepts when a prefix in $L_1$ leads into a suffix in $L_2$. Careful handling of start/accept states and $\epsilon$-closures is required.

Front

Kleene Star

Back

To implement $L^*$ build an NFA that allows repeating the machine for $L$ any number of times by adding $\epsilon$-transitions from accept states back to the start and from a new start to the old start. Also make the new start an accept state to allow zero repetitions (the $\epsilon$ string). This construction shows closure under the star operation.

Front

Intersection Construction

Back

Intersection of two regular languages is usually implemented by the DFA product construction where states are pairs and a pair is accepting only if both components are accepting. This yields a DFA recognizing $L_1\cap L_2$. Intersection closure can also be derived from closure under complement and union using De Morgan’s laws.

Front

Complement of Regular

Back

To complement a regular language given by a DFA, make the DFA total (define missing transitions to a sink) and swap accepting and non-accepting states. The resulting DFA recognizes the complement language. Complement closure relies on determinism, so converting NFAs to DFAs may be needed first.

Front

Pumping Lemma

Back

The pumping lemma for regular languages gives a necessary property: any sufficiently long string $s$ in an infinite regular language can be split $s=xyz$ with $|xy|\le p$, $|y|>0$, and $xy^iz\in L$ for all $i\ge0$. It is used primarily to prove languages non-regular by deriving contradictions. Remember to choose $p$ and reason about all possible splittings.

Front

Finiteness vs Infiniteness

Back

For a regular language, finiteness can be decided by inspecting its DFA for reachable cycles: if a cycle is reachable from the start and leads to an accept state, the language is infinite. If no such cycle exists, the language is finite. This is decidable because DFAs are finite graphs.

Front

Constructing a Finite Automaton

Back

Constructing an FA from a language description means designing states and transitions to track necessary information (e.g., recent symbols, parity, or counts modulo some number). Start with a clear invariant for each state and ensure transitions preserve it. Validate the design by tracing sample strings and proving correctness formally if needed.

Front

Show Acceptance

Back

To show a finite automaton accepts a particular string, present a valid sequence of state transitions consistent with the input that ends in an accepting state. For an NFA show at least one accepting path, including any $\epsilon$-moves and closures used. For a DFA the unique run suffices and can be traced step by step.

Front

Subset Construction

Back

The subset construction converts an NFA to an equivalent DFA by making each DFA state represent a set of NFA states (typically their $\epsilon$-closure). The start state is the $\epsilon$-closure of the NFA start, and transitions map to closures of reachable sets. This produces a (possibly exponentially larger) deterministic machine recognizing the same language.

Front

State Elimination

Back

State elimination converts a finite automaton into a regular expression by iteratively removing states and replacing transitions with regex labels that preserve the same language between remaining states. One typically introduces a single start and single accept state and carefully updates transition expressions until only those two states remain. The final label is a regular expression for the language.

Front

Thompson Construction

Back

Thompson’s construction builds an $\epsilon$-NFA from a regular expression in a recursive, mechanical way, handling union, concatenation, and star with small gadget automata connected by $\epsilon$-transitions. The resulting NFA has size linear in the regex and is easy to simulate or convert to a DFA. It’s the standard method to prove regex-to-FA equivalence.

Front

Membership Testing

Back

To determine if a string belongs to a regular language, simulate its DFA in time linear in the string length by following transitions. For an NFA, compute reachable states stepwise using $\epsilon$-closures and transitions (or convert to a DFA first). These procedures decide membership because regular languages are decidable.

Front

DFA Minimization

Back

DFA minimization reduces a DFA to a smallest equivalent DFA by merging equivalent states, typically using partition refinement (Hopcroft’s algorithm) or table-filling methods. The minimal DFA is unique up to renaming states and is useful for canonical representations and equivalence checks. Minimization also helps prove non-equivalence by comparing reduced forms.

Front

Automata Equivalence Test

Back

Two automata are equivalent if their symmetric difference language is empty; construct a product automaton that accepts strings where the machines disagree and test emptiness. Emptiness of a DFA is decidable via reachability to an accept state. This yields a practical method to prove or disprove language equality between machines.