Finite automata, regular languages, and Turing machine concepts from an intro theory of computation course.
35 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a deterministic finite automaton (DFA)?
Show answer
A finite automaton where each state has exactly one transition for each input symbol.- What is a nondeterministic finite automaton (NFA)?
Show answer
A finite automaton where a state may have zero, one, or more transitions for each input symbol.- How do DFA and NFA differ in their transition functions?
Show answer
DFA: one transition per input symbol per state. NFA: zero or more transitions per input symbol per state.- What is an accept state (or final state) in an automaton?
Show answer
A designated state such that a string is accepted by the automaton if and only if it ends in an accept state after reading the entire input.- Can every NFA be converted to an equivalent DFA?
Show answer
Yes, using the subset construction, where each DFA state represents a set of NFA states.- When does a DFA accept a string?
Show answer
When following the transitions for each input symbol in sequence leads to an accept state after the final symbol is consumed.- What is the language of an automaton?
Show answer
The set of all strings that the automaton accepts.- What is a regular language?
Show answer
A language that can be recognized by some finite automaton (equivalently, described by a regular expression).- What is a regular expression?
Show answer
A notation for describing regular languages using the operations union, concatenation, and Kleene star over an alphabet.- What is the relationship between finite automata and regular expressions?
Show answer
Every language describable by a regular expression is accepted by some finite automaton, and vice versa.- Are regular languages closed under union?
Show answer
Yes. If L1 and L2 are regular, then L1 union L2 is regular.- Are regular languages closed under concatenation?
Show answer
Yes. If L1 and L2 are regular, then L1 concatenated with L2 is regular.- Are regular languages closed under Kleene star?
Show answer
Yes. If L is regular, then L* is regular.- Are regular languages closed under complement?
Show answer
Yes. If L is regular, then the complement of L (all strings not in L) is regular.- Are regular languages closed under intersection?
Show answer
Yes. If L1 and L2 are regular, then L1 intersected with L2 is regular.
FlashKeepers