Lecture: DFA and Regular Languages (Vocabulary)

Vocabulary flashcards covering key terms from the lecture notes on DFAs, regular languages, and related concepts.

Deterministic Finite Automata (DFA)

A finite automaton where, for every state and input symbol, there is exactly one next state; computes a single path for each input and either accepts or rejects.

Finite Automaton

A theoretical machine with finite memory used to recognize patterns; can be deterministic (DFA) or nondeterministic (NFA).

Alphabet (Σ)

A finite set of symbols from which input strings are formed and that appear in the automaton's transitions.

State (Q)

A configuration or condition of the automaton; elements of the finite set of states it can be in.

Start State (q0)

The state in which computation begins for every input string.

Accept State / Final State (F)

State(s) in which, if the machine ends after reading the input, the string is accepted.

Transition Function (δ)

The function that maps a state and an input symbol to the next state: δ: Q × Σ → Q.

Language recognized by a machine L(M)

The set of strings over Σ that M accepts; the language described by the machine.

Regular Language

A language that can be recognized by some finite automaton (or described by a regular expression).

String

A finite sequence of symbols drawn from the alphabet Σ.

epsilon (ε)

The empty string, a string of length zero.

Substring 11

A language A = { w | w contains the substring 11 }; a regular language example.

Even number of 1s language

The language B = { w | w has an even number of 1s }; regular and recognizable by a parity-tracking DFA.

Equal number of 0s and 1s language

The language C = { w | w has an equal number of 0s and 1s }; not regular and not recognizable by any DFA.

5-tuple DFA definition

A DFA is defined as M = (Q, Σ, δ, q0, F), a 5-tuple consisting of states, alphabet, transition function, start state, and accept states.

Universe (Σ*)

'Σ*' is the set of all strings over the alphabet Σ; used as the universal set for operations like complement.

Complement (of a language)

The set of strings over Σ that are not in the language, relative to a fixed universe (often Σ*).

Regular Expressions

A notation for describing regular languages; regular languages are closed under operations like union and concatenation.

Memory in DFA

DFAs have finite memory (finite number of states) and cannot remember arbitrary-length strings or perform unbounded counting.

DFA Design

The process of constructing a DFA by determining what information to remember about the input and how states reflect that information (e.g., parity).

Parity (even/odd)

A property used in DFA design to track evenness or oddness of counts (e.g., number of 1s read so far).

Σ = {0,1}

A common binary alphabet used in many DFA examples.

Accepting a string

Process where, after reading the entire input, the machine ends in an accept state so the string is in the language L(M).

Nonregular Language

A language that cannot be recognized by any DFA; often requires unbounded memory to decide.

M2 (even number of 1s)

A two-state DFA that tracks the parity of the number of 1s read; 1 toggles parity, 0 leaves parity unchanged.

M3 (starts and ends with same symbol)

A DFA with multiple states that recognizes languages like C = { w | w starts and ends with the same symbol }; an example of a regular language.

E2 and E3 (complementation example)

Languages E2 and E3 used to illustrate taking complements relative to a universe; E2 recognizes the complement of E3 with respect to Σ*.

Closure under union

Regular languages are closed under union: the union of two regular languages is regular.

Closure under concatenation

Regular languages are closed under concatenation: the concatenation of two regular languages is regular.

DFA Formal Definition

A DFA is defined as M = (Q, Σ, δ, q0, F); Q is finite, Σ is finite, δ is the transition function, q0 is the start state, F is the set of accept states.