DFA_flashcards
(20 cards)
What is an alphabet (Σ) in formal language theory?
A finite, nonempty set of symbols.
What is a word in formal language theory?
A finite (possibly empty) sequence of symbols from an alphabet Σ.
What is the notation Σ* used for?
It denotes the set of all possible words (including the empty word) over the alphabet Σ.
Give an example of Σ and Σ*.
If Σ = {0, 1}, then Σ* includes words like 101, 11001, etc.
What is a language L over an alphabet Σ?
A subset of Σ*, i.e. any set of words formed from Σ.
What does the symbol ε represent?
The empty word.
What does |w| mean in formal language theory?
It denotes the length of the word w.
What is wᴿ in language theory?
It is the reverse of the word w.
What is a palindrome?
A word w such that wᴿ = w (it reads the same forward and backward).
What does uv mean in string operations?
It is the concatenation of words u and v.
What does aⁿ represent?
n repetitions of the symbol a.
What is a subword?
A word u is a subword of v if v = w₁uw₂ for some w₁, w₂.
What is the formal definition of a DFA?
A DFA is a 5-tuple (Q, Σ, δ, s, F) where Q is a set of states, Σ is the alphabet, δ is the transition function, s is the start state, and F is the set of accepting states.
What is the transition function δ in a DFA?
A function δ: Q × Σ → Q defining the next state based on current state and input.
What is the acceptance condition for a DFA?
A DFA accepts a word if, starting from the start state, it follows transitions for each symbol in the word and ends in an accepting state.
How is the language of a DFA A defined?
L(A) = { w ∈ Σ* | A accepts w }
What is a regular language?
A language L is regular if there exists a DFA A such that L = L(A).
What is an example of a regular language with even number of 0s?
L = { w ∈ {0,1}* | w contains an even number of 0s }
Give an example of a regular language that accepts aⁿbᵐ.
L = { aⁿbᵐ | n, m ≥ 0 }
Give an example of a regular language that accepts strings containing 100 as a subword.
L = { w ∈ {0,1}* | w contains 100 } — DFA tracks progress toward seeing 100.
