Revision approach
- Language–grammar–recognizer connections
- Weaker-model limitation proofs
- Computability versus resource complexity
- Explicit alphabets and epsilon conventions
- Decision formulations and reduction directions
👁 Full explanation
Connect a language to a grammar and recognizer, prove limits of weaker models, and distinguish computability from resource complexity. State alphabets, epsilon conventions, decision formulations and reduction directions explicitly when solving automata and complexity problems. - Construct and justify recognizers
- DFA; grammar; PDA design
- Invariant
- Soundness and completeness
- Examples alone insufficient
👁 Full explanation
Design a DFA/grammar/PDA and justify its invariant, soundness and completeness, not merely examples. - Pumping proof quantifier order
- Pumping length before witness
- Every allowed split defeated
👁 Full explanation
For pumping, choose a witness after the pumping length and defeat every allowed split. - Reduction proof obligations
- Explicit map
- Time/computability bound
- Yes and no implications
- Known-hard source → new target
👁 Full explanation
For reductions, write the map, the time/computability bound and both yes/no implications; known-hard source reduces to new target. - Separate classification questions
- Language hierarchy
- Decidability
- Complexity
- Recalculate symbols and options
- Highlighted-key trap
👁 Full explanation
Treat language hierarchy, decidability and complexity as separate questions. Recalculate symbols and evaluate each choice using language and machine definitions.
AUT01
Symbols, alphabets, words and length
[Exam Focus]- Alphabet, word and language
- Σ: finite symbol set
- String: finite ordered symbol sequence
- L⊆Σ*
- Empty word ε=λ; length zero
- ∅: no words
- {ε}: one word
- ε and ∅ ≠ numeric 0
👁 Full explanation
An alphabet Σ is a finite set of symbols. A word/string is a finite ordered sequence of symbols from Σ; a language is a set of words, L⊆Σ*. An empty word ε, also written λ, has length zero. The empty language ∅ contains no words; {ε} contains one. Neither ε nor ∅ is the numeric symbol 0. - Length versus word powers
- Occurrences, not distinct symbols
- |caddba|=6
- |caddba|²=36
- |(caddba)²|=12
- Exponent placement trap
- Choice repair requires changed expression
👁 Full explanation
Length counts occurrences, not distinct symbols: |caddba|=6, so |caddba|²=36. By contrast |(caddba)²|=12 because the word is concatenated twice. Distinguish |Z|², the square of a word’s length, from |Z²|, the length of its repeated concatenation; keep the exponent in its stated position.
3 related practice questions
Blueprint: LO1 · Note references: AUT-MOD, AUT-NOTE
- Alphabet, word and language
AUT02
Concatenation, powers and reversal
- Concatenation, powers and reversal
- cddc·ababb=cddcababb
- Order generally matters
- εx=xε=x
- x⁰=ε; xⁿ: n copies
- caddbaᴿ=abddac
- (xy)ᴿ=yᴿxᴿ
- (xᴿ)ᴿ=x
👁 Full explanation
Concatenation xy writes x followed by y: cddc·ababb=cddcababb; order generally matters. εx=xε=x. Define x⁰=ε and xⁿ as n copies for n≥1. Reverse xᴿ reads symbols backward: caddba reverses to abddac; (xy)ᴿ=yᴿxᴿ and (xᴿ)ᴿ=x. - Language concatenation and powers
- LM={xy:x∈L,y∈M}
- L⁰={ε}; Lⁿ⁺¹=LⁿL
- {e,fgh}{c,d}={ec,ed,fghc,fghd}
- fghe absent
- L⁰=ε: missing-braces type error
- Case-sensitive symbols
- Uppercase/lowercase transcription requires declared repair
👁 Full explanation
For languages, LM={xy:x∈L,y∈M}, L⁰={ε}, and Lⁿ⁺¹=LⁿL. Thus {e,fgh}{c,d}={ec,ed,fghc,fghd}; fghe is absent. A language power is a set, so L⁰=ε is a type error unless braces are understood. Symbols are case-sensitive; uppercase symbols do not equal lowercase symbols unless a conversion is explicitly specified.
4 related practice questions
Note references: AUT-MOD, AUT-NOTE
- Concatenation, powers and reversal
AUT03
Language Operations and Empty-Word Cases
[Exam Focus]- Alphabet closures and word counts
- Σⁿ: exactly n symbols
- |Σ|=k ⇒ |Σⁿ|=kⁿ
- Σ⁰={ε}
- Σ*=⋃n≥0Σⁿ
- Σ⁺=⋃n≥1Σⁿ
- Nonempty alphabet: ε∉Σ⁺
- Σ*=Σ⁺∪{ε}
- {a,b}²={aa,ab,ba,bb}
👁 Full explanation
Σⁿ contains words of exactly n symbols; for |Σ|=k, |Σⁿ|=kⁿ, including Σ⁰={ε}. Σ*=⋃n≥0Σⁿ and Σ⁺=⋃n≥1Σⁿ. Over a nonempty alphabet, Σ⁺ excludes ε and Σ*=Σ⁺∪{ε}. Σ² over {a,b} is {aa,ab,ba,bb}. - Language operations and empty cases
- L*=⋃n≥0Lⁿ; L⁺=LL*
- ε∈L ⇒ ε∈L⁺
- Alphabet positive-closure distinction
- ∅*={ε}; ∅⁺=∅
- {ε}*={ε}
- Union: either set
- Intersection: same word in both
- Intersection ≠ concatenation
- Complement Σ*−L: fixed alphabet
👁 Full explanation
For an arbitrary language L, L*=⋃n≥0Lⁿ and L⁺=LL*. Unlike alphabet positive closure, L⁺ can contain ε when ε∈L. ∅*={ε}, ∅⁺=∅, and {ε}*={ε}. Union means membership in either set; intersection requires the same word in both, not concatenation. Complement is Σ*−L and needs a fixed alphabet.
12 related practice questions
Blueprint: LO1 · Note references: AUT-MOD, AUT-NOTE
- Alphabet closures and word counts
AUT04
Grammars generate; automata recognize
[Exam Focus]- Grammar versus recognizer
- G=(V,Σ,P,S)
- Finite variables; disjoint terminals
- Productions; start S∈V
- Left-side replacement
- L(G)={w∈Σ*:S⇒*w}
- Grammar: language generation
- Automaton: word acceptance/language recognition
- Automata recognize languages, not grammars
👁 Full explanation
Write G=(V,Σ,P,S): finite variables V, terminals Σ disjoint from V, productions P and start variable S∈V. A production replaces its left side by its right side. The language is L(G)={w∈Σ*:S⇒*w}. A recognizer processes a word and accepts exactly the language members. Grammars generate languages; automata recognize languages, not grammars. - Language equivalence and notation
- Equivalent grammars: equal generated languages
- Rule counts/names irrelevant
- Common word insufficient
- Equal alphabets insufficient
- One-way inclusion insufficient
- RE denotes language, not word set
- Formal examples: precisely specified sets
- Natural-language example trap
👁 Full explanation
Two grammars are equivalent when their generated languages are equal, regardless of rule counts or variable names. One common word, equal alphabets or one-way inclusion is insufficient. A regular expression denotes a language but is not itself the set of matched words. Natural languages such as English are not the intended formal-language examples; give a precisely specified set instead.
9 related practice questions
Blueprint: LO1 · Note references: AUT-MOD, AUT-NOTE, AUT-BLUEPRINT
- Grammar versus recognizer
AUT05
Chomsky Hierarchy and Epsilon Conventions
[Exam Focus]- Chomsky model correspondences
- Type 3 REG ↔ finite automata
- Type 2 CFG ↔ NPDA
- Type 1 CSL ↔ nondeterministic LBA
- Context-sensitive/noncontracting grammars
- Type 0 unrestricted ↔ Turing recognizers
- Unrestricted α→β: variable in α
- Meaningless arbitrary rewrite trap
👁 Full explanation
Type 3 regular grammars correspond to finite automata; type 2 CFGs to nondeterministic PDAs; type 1 context-sensitive/noncontracting grammars to nondeterministic LBAs; type 0 unrestricted grammars to Turing recognizers. In an unrestricted production α→β, α contains at least one variable; unrestricted does not mean any meaningless rewrite is allowed. - Expressiveness hierarchy and ε exception
- REG⊊CFL⊊CSL⊊DECIDABLE⊊RE
- Optional S→ε; S absent from RHS
- Strict noncontracting rules cannot generate ε
- Stronger models include weaker languages
- Capable-family questions: potentially nonunique
- Least sufficient versus exact equivalent family
- Expressiveness ≠ runtime ranking
👁 Full explanation
Use REG ⊊ CFL ⊊ CSL ⊊ DECIDABLE ⊊ RE, under the usual convention allowing S→ε with S absent from right sides when needed. Strict noncontracting grammars otherwise cannot generate ε. Stronger families can describe lower-family languages: asking which grammar is capable is often nonunique. Ask for the least sufficient family or the exact family equivalent to a machine model. This is an expressiveness hierarchy, not a runtime ranking.
26 related practice questions
Blueprint: LO1, LO2 · Note references: AUT-MOD, AUT-NOTE, AUT-BLUEPRINT
- Chomsky model correspondences
AUT06
DFA definition and acceptance
[Exam Focus]- DFA formal definition
- M=(Q,Σ,δ,q₀,F)
- Finite nonempty Q; q₀∈Q
- F⊆Q, possibly empty
- Total δ:Q×Σ→Q
- One successor per state/symbol pair
- One-transition-machine misconception
- Empty F recognizes ∅
- State names ≠ acceptance status
👁 Full explanation
A deterministic finite automaton (DFA) is M=(Q,Σ,δ,q₀,F), with finite nonempty Q, start q₀∈Q, accepting set F⊆Q and total δ:Q×Σ→Q. Exactly one next state is specified per state/symbol pair; this does not mean the whole machine has one transition. F may be empty, recognizing ∅. State names q₀,q₁,… do not determine accepting status. - DFA acceptance and memory
- Entire input consumed
- Ending state in F
- Earlier accepting visit insufficient
- ε accepted iff q₀∈F
- Rejecting sink: all-symbol self-loops
- Sink still finishes finite input
- Finite state-encoded memory
- Finite memory ≠ no memory
👁 Full explanation
Start at q₀ and consume the entire input. Accept iff the ending state is in F; visiting an accepting state earlier is insufficient. ε is accepted exactly when q₀∈F. A nonaccepting sink loops on every symbol and cannot reach acceptance; it still finishes after finite input. Finite automata have finite memory encoded by states, not no state or no ability to remember any history.
11 related practice questions
Blueprint: LO1 · Note references: AUT-MOD, AUT-NOTE
- DFA formal definition
AUT07
Finite-State Recognizer Design and Traces
[Exam Focus]- Suffix-invariant DFA design
- Binary ending 01
- q₀: no useful suffix
- q₁: suffix 0; q₂: suffix 01
- Only q₂ accepts
- (0,1): q₀→(q₁,q₀)
- (0,1): q₁→(q₁,q₂)
- (0,1): q₂→(q₁,q₀)
- 10101: q₀,q₀,q₁,q₂,q₁,q₂
- Final q₂: accepted
👁 Full explanation
Choose states with invariant meanings: the information about the consumed prefix needed to decide future acceptance. For binary words ending 01 use q₀=no useful suffix, q₁=last suffix 0, q₂=last suffix 01; only q₂ accepts. Transitions on (0,1) are q₀→(q₁,q₀), q₁→(q₁,q₂), q₂→(q₁,q₀). Input 10101 follows q₀,q₀,q₁,q₂,q₁,q₂ and accepts. - Length-at-least-two DFA
- States: 0, 1, ≥2 symbols
- Every symbol advances count stage
- Third state: accepting loop
- q₂ naming arbitrary
- Missing diagram/meanings: no numbered answer
- Test ε and shortest boundary words
- Test overlaps
- Sample agreement ≠ proof
👁 Full explanation
For length at least two use meanings 0 symbols, 1 symbol, at least 2 symbols. Every input advances toward the third state, which loops and accepts. Calling it q₂ is a naming choice: without a diagram or state definitions no numbered-state answer follows. To verify a design, test ε, shortest accepted/rejected words and overlaps; sample agreement alone is not a proof.
Blueprint: LO3 · Note references: AUT-MOD, AUT-NOTE, AUT-BLUEPRINT
- Suffix-invariant DFA design
AUT08
Minimum States for Prefixes and Suffixes
[Exam Focus]- Fixed-suffix DFA minimum
- Valid word length n: n+1 states
- Longest suffix matching pattern prefix
- Overlapping-prefix fallback transitions
- Distinguishable prefixes via continuations
- Lower-bound proof
- Unnecessary rejecting-sink trap
👁 Full explanation
For a fixed valid word w of length n, a DFA for strings ending in w needs n+1 states representing the longest consumed suffix that is a prefix of w. Overlapping prefixes determine fallback transitions. Distinct prefixes are distinguishable by suitable continuations, proving the lower bound; do not add an unnecessary rejecting sink. - Fixed-prefix DFA minimum and alphabet
- n matched-prefix stages
- Accepting continuation and rejecting sink
- n≥1, mismatches possible: n+2
- Unary alphabet: potentially unreachable sink
- Pattern symbol outside Σ: empty language
- Empty-language minimum: one rejecting state
- Starting abc over {a,b}: one state
- Five requires alphabet containing a,b,c
👁 Full explanation
For strings starting with w, a complete DFA ordinarily has n matched-prefix stages, an accepting continuation state and a rejecting sink: n+2 when n≥1 and the alphabet allows mismatches. Over a unary alphabet the sink may be unreachable. If w contains a symbol outside Σ, the language is empty, whose minimal complete DFA has one rejecting state. Thus starting abc over {a,b} needs one state, not five; five requires an alphabet containing a,b,c.
2 related practice questions
Blueprint: LO3 · Note references: AUT-MOD, AUT-NOTE
- Fixed-suffix DFA minimum
AUT09
NFA and epsilon transitions
[Exam Focus]- NFA and ε-NFA
- δ:Q×Σ→𝒫(Q)
- Zero, one, many successors
- ε-NFA domain: Q×(Σ∪{ε})
- ε moves consume nothing
- NFA convention varies
- Existential finite accepting path
- Complete word consumed
- ε moves before/after input symbols
- Other paths may get stuck
👁 Full explanation
A nondeterministic finite automaton (NFA) permits zero, one or many successors: δ:Q×Σ→𝒫(Q). An ε-NFA additionally permits moves without consuming input, using domain Q×(Σ∪{ε}). Some books include ε moves in the term NFA; state the convention. An NFA accepts iff at least one finite path consumes the complete word and finishes in F, including permitted ε moves before/after symbols. Other paths may get stuck. - NFA versus DFA power
- Both recognize exactly REG
- Nondeterminism: potentially smaller description
- DFA successor as singleton set
- ε ≠ input character
- ε ≠ permission for unread input
👁 Full explanation
An NFA is not more expressive than a DFA: both recognize exactly REG. Nondeterminism can make a description smaller. A DFA is a special NFA after interpreting its unique successor as a singleton set. ε is a zero-input move, not an ordinary input character or permission to accept with unread input.
7 related practice questions
Blueprint: LO1, LO2 · Note references: AUT-MOD, AUT-NOTE
- NFA and ε-NFA
AUT10
Subset construction with epsilon closure
[Exam Focus]- Subset construction with ε-closure
- ε-closure(T): T plus ε-reachable states
- Start: ε-closure({q₀})
- Symbol step: ε-closure(⋃q∈Tδ(q,a))
- Accepting subset intersects F
- Reachable subsets only
- Empty subset: rejecting sink if reached
- n-state NFA: at most 2ⁿ states
- Exactly-2ⁿ trap
👁 Full explanation
ε-closure(T) contains T and every state reachable through ε moves. Start the DFA at ε-closure({q₀}); for each current subset T and symbol a compute ε-closure(⋃q∈Tδ(q,a)). A subset accepts iff it intersects F. Explore only reachable subsets; the empty subset is the rejecting sink when reached. An n-state NFA yields at most 2ⁿ DFA states, not necessarily exactly 2ⁿ. - Subset-construction example
- Σ={a}; start p; final r
- δ(p,a)={p,r}; δ(r,a)=∅
- Start {p}
- a→{p,r}; further a self-loop
- Accepted language a⁺
- Added ε edge p→r
- Start already accepting; ε accepted
👁 Full explanation
Example over Σ={a}: states p,r, start p, final r; δ(p,a)={p,r}, δ(r,a)=∅. The subset machine starts {p}, reaches {p,r} on a, and stays there on further a's. It accepts a⁺. With an ε edge p→r, the starting subset would already contain r and ε would also be accepted.
3 related practice questions
Blueprint: LO3 · Note references: AUT-MOD, AUT-GUIDE, AUT-SUBSET
- Subset construction with ε-closure
AUT11
Equivalence, minimization and diagram checks
[Exam Focus]- DFA minimization
- Discard unreachable states
- Initial accepting/nonaccepting partition
- Split by transition target blocks
- Repeat until stable
- Stable equivalence classes merged
- Equivalent: every continuation agrees
- Current acceptance alone insufficient
👁 Full explanation
First discard unreachable DFA states. Partition remaining states into accepting/nonaccepting blocks; repeatedly split a block when two states transition on some symbol into different blocks. Stable blocks are equivalence classes and can be merged. Equivalent states have identical acceptance for every continuation; current acceptance alone is insufficient. - Equivalence and diagram checks
- Reachable product-state pairs
- Exactly one accepting: distinguishing word
- No disagreement: language equality
- Complete partial diagram with sink
- RE test: ε and shortest cycles
- Accepting start plus ab return
- Equivalent expression must include ε,ab
👁 Full explanation
For DFA equivalence build pairs of states and search from the start pair. Any reachable pair with exactly one accepting component supplies a distinguishing word; if none exists, the languages agree. A partial diagram must first be completed consistently with a sink. To reject a proposed RE quickly, compare ε and the shortest cycles: an accepting start plus an ab return cycle forces ε and ab into the language. Every equivalent expression must contain both.
1 related practice question
Blueprint: LO3 · Note references: AUT-MOD, AUT-GUIDE, AUT-EQUIV
- DFA minimization
AUT12
Regular-expression notation and precedence
- Classical RE syntax and precedence
- ∅; ε; symbols; union; concatenation; star
- Union: A|B or A+B
- Postfix r⁺: one-or-more
- Distinct uses of +
- Parenthesize conflicting conventions
- Star > concatenation > union
- r?=r|ε
- r⁺=rr*
👁 Full explanation
Classical expressions use ∅, ε, symbols, union, concatenation and star. A union B is written A|B or A+B; postfix r⁺ means one-or-more r repetitions and is a different use of +. Parenthesize when conventions might clash. Star binds tightest, concatenation next, union last. r? means r|ε; r⁺=rr*. - RE interpretation examples
- (a|b)*a: ending a
- 0*10*: exactly one 1
- a*(b|c): a's then one b/c
- aab accepted; aaa,aaabc rejected
- (0|ε)(0|1)*: all binary words
- ε alternative permits any suffix
- Programming backreferences may exceed REG
- Wildcard dot: additional notation
👁 Full explanation
(a|b)*a denotes words ending a; 0*10* denotes exactly one 1; a*(b|c) gives zero-or-more a's then exactly one b or c, so aab belongs but aaa and aaabc do not. (0|ε)(0|1)* is simply all binary words because ε permits any suffix. Programming regex features such as backreferences may exceed classical regular-language power; wildcard dot is an extra notation, not a basic alphabet-independent theorem.
4 related practice questions
Note references: AUT-MOD, AUT-NOTE
- Classical RE syntax and precedence
AUT13
Regular Expressions and Representation Conversions
[Exam Focus]- Build regular expressions
- At least one a: (a|b)*a(a|b)*
- Exactly one a: b*ab*
- At least two zeros: (0|1)*0(0|1)*0(0|1)*
- Nonadjacent zeros allowed
- 010 distinguishes from substring 00
- S→aS|ε generates a*
👁 Full explanation
To require at least one a anywhere over {a,b}, use (a|b)*a(a|b)*. b*ab* requires exactly one a. At least two zeros uses (0|1)*0(0|1)*0(0|1)*; the zeros need not be adjacent. Testing 010 distinguishes it from a requirement for substring 00. For S→aS|ε, any number of a's is generated, giving a*. - RE–automaton conversions
- RE→ε-NFA fragments
- Union: parallel alternatives
- Concatenation: connected fragment ends
- Star: ε bypass and repetition
- Then subset construction
- Automaton→RE: state elimination
- rᵢⱼ | rᵢₖ(rₖₖ)*rₖⱼ
- New start/final nodes when required
- Whole-language preservation
👁 Full explanation
RE→automaton uses ε-NFA fragments: parallel alternatives for union, connect accepting ends to the next fragment for concatenation, and add bypass/repetition ε moves for star. Then apply subset construction. For automaton→RE, eliminate a state k while updating edge i→j as rᵢⱼ | rᵢₖ(rₖₖ)*rₖⱼ; include new start/final nodes where required. These operations preserve the whole language, not just tested examples.
3 related practice questions
Blueprint: LO1, LO3 · Note references: AUT-MOD, AUT-GUIDE, AUT-RECONVERT
- Build regular expressions
AUT14
Regular grammars and closure constructions
[Exam Focus]- Regular grammar orientations
- Right-linear: A→aB, A→a, permitted ε
- Left-linear: A→Ba
- Consistent orientation: REG
- Arbitrary mixing may be nonregular
- S→aA|ε, A→Sb: aⁿbⁿ
- A→aBA: CFG, not regular form
👁 Full explanation
Right-linear rules have form A→aB, A→a or permitted ε rules; left-linear rules put the single variable at the opposite end, A→Ba. Both consistent orientations generate REG; arbitrarily mixing them can generate nonregular languages, for example S→aA|ε, A→Sb generates aⁿbⁿ. A CFG rule A→aBA is legal but not regular-grammar form. - Regular constructions and closure
- Variables → NFA states
- A→aB: a edge
- A→a: fresh final state
- A→ε: accepting A
- Union; concatenation; star; reversal
- Intersection; difference; complement
- Reversal: reverse edges, swap start/finals
- ε-NFA handles reversed starts
- Complement: complete DFA, swap acceptance
- Product states: intersection/difference
👁 Full explanation
For right-linear grammar→NFA, variables become states, A→aB becomes an a edge, A→a leads to a fresh final state, and A→ε makes A accepting. Regular languages are closed under union, concatenation, star, reversal, intersection, difference and complement. Reverse edges and exchange start/final roles using an ε-NFA to obtain reversal. Complement requires a complete DFA; then swap accepting/nonaccepting states. Product-state constructions implement intersection/difference.
6 related practice questions
Blueprint: LO1, LO2, LO3 · Note references: AUT-MOD, AUT-NOTE, AUT-CLOSURE
- Regular grammar orientations
AUT15
Regular pumping lemma: use the quantifiers
[Exam Focus]- Regular pumping lemma
- ∃p≥1; ∀s∈L, |s|≥p
- s=xyz; |xy|≤p; |y|≥1
- ∀i≥0: xyⁱz∈L
- Nonregular proof: arbitrary p, chosen witness
- Every allowed split broken
- One bad split insufficient
- Necessary condition ≠ regularity proof
👁 Full explanation
If L is regular, some p≥1 satisfies: every s∈L with |s|≥p has a split s=xyz, |xy|≤p, |y|≥1, and xyⁱz∈L for every i≥0. To disprove regularity, assume an arbitrary pumping length p, choose s, then show every allowed split can be broken by some i. Finding one bad split proves nothing; satisfying this necessary condition alone does not prove regularity. - Pumping aⁿbⁿ and infinitude
- Witness aᵖbᵖ
- Every split: y=aᵏ, k≥1
- i=0: fewer a's than b's
- Contradiction excludes every DFA
- n-state DFA: long path repeats state
- Accepted cycle: indefinite repetition
- Infinite iff accepted word length ≥n
👁 Full explanation
For L={aⁿbⁿ:n≥0}, choose aᵖbᵖ. Every allowed y=aᵏ with k≥1; pumping i=0 leaves fewer a's than b's. The contradiction excludes every DFA. For an n-state DFA, an accepted word of length at least n repeats a state along its path, giving an accepted cycle that can be repeated indefinitely. Thus a fixed DFA's language is infinite iff it has an accepted word of length at least its state count.
5 related practice questions
Blueprint: LO2 · Note references: AUT-MOD, AUT-NOTE
- Regular pumping lemma
AUT16
CFG derivations, sentences and parse trees
[Exam Focus]- CFG productions and sentential forms
- A→α; A∈V; α∈(V∪Σ)*
- One variable on left
- Weaker set-membership options also true
- Sentential form: any S-derived string
- Includes terminal sentences and S
👁 Full explanation
In a context-free grammar (CFG) each production has one variable on the left, A→α with α∈(V∪Σ)*. The left side therefore also belongs to V∪Σ and its string closure; alternatives stating these weaker memberships can all be true. A sentential form is any string derived from S, including terminal-only sentences and S itself. - Derivations and parse trees
- Leftmost: leftmost variable replacement
- Rightmost: rightmost variable replacement
- Not opposite input-scanning directions
- Root S; expanded internal variables
- Terminal leaves; optional ε leaves
- Left-to-right yield
- Tree: derivation structure
- Derivation-graph path: different object
👁 Full explanation
A leftmost derivation always replaces the leftmost variable; a rightmost one replaces the rightmost variable. This is not scanning the completed input in opposite directions. A complete parse tree has root S, internal variable nodes expanded by productions and terminal leaves, with ε leaves when that convention is used. Read the leaves left-to-right for the yielded word. The whole tree represents derivation structure; a path in a derivation graph is a different object.
9 related practice questions
Blueprint: LO1 · Note references: AUT-MOD, AUT-NOTE
- CFG productions and sentential forms
AUT17
Design and validate context-free grammars
[Exam Focus]- Matched-structure CFG design
- Recursive rule plus stopping base
- S→aSb|ε: aⁿbⁿ, n≥0
- n recursions: n matched pairs
- S⇒aSb⇒aaSbb⇒aabb
- n≥1: base ab replaces ε
👁 Full explanation
Use a recursive rule to enforce matched structure and a base rule to stop. S→aSb|ε generates exactly aⁿbⁿ for n≥0: n recursive steps add n a's on the left and n b's on the right. Derive aabb by S⇒aSb⇒aaSbb⇒aabb. For n≥1 replace ε by base ab. - CFG construction and proof
- aⁿbᵐ, n>m≥0
- S→aSb|A; A→aA|a
- S: matched pairs; A: extra a's
- Balanced parentheses: S→(S)S|ε
- Soundness: preserved intended property
- Completeness: decompose desired words
- Several examples ≠ language equality
👁 Full explanation
For aⁿbᵐ with n>m≥0, use S→aSb|A and A→aA|a: each S recursion adds a matched pair, then A adds at least one extra a. For balanced parentheses use S→(S)S|ε. Validate soundness—each rule preserves the intended property—and completeness—decompose any desired nonempty word into pieces matching a production. Merely producing several examples does not establish exact language equality.
4 related practice questions
Blueprint: LO2, LO3 · Note references: AUT-MOD, AUT-NOTE, AUT-BLUEPRINT
- Matched-structure CFG design
AUT18
Ambiguity and precedence
[Exam Focus]- CFG ambiguity
- One word, two distinct parse trees
- Equivalent: two distinct leftmost derivations
- Same-tree expansion orders insufficient
- E→E+E|E*E|id
- id+id*id: (id+id)*id versus id+(id*id)
👁 Full explanation
A CFG is ambiguous when some word has two distinct parse trees, equivalently two different leftmost derivations. Different expansion orders that give the same tree do not prove ambiguity. E→E+E|E*E|id allows id+id*id to group as (id+id)*id or id+(id*id). - Precedence and ambiguity distinctions
- E→E+T|T; T→T*F|F; F→id|(E)
- Multiplication before addition
- Left recursion: left association
- Uniqueness: last-operator split and induction
- S→SS|ε: ambiguous ε
- S→A|B; both branches derive ab
- A→ab; B→abB|ε
- Ambiguous grammar ≠ inherently ambiguous language
- Alternative grammar may remove ambiguity
👁 Full explanation
Separate precedence levels: E→E+T|T, T→T*F|F, F→id|(E). Multiplication binds inside T before addition at E, and left recursion encodes left association. Uniqueness follows by the top-level last operator split and induction. S→SS|ε is already ambiguous for ε. S→A|B is ambiguous if A→ab and B→abB|ε both produce ab. Ambiguous grammar and inherently ambiguous language differ: another grammar may remove ambiguity.
4 related practice questions
Blueprint: LO3 · Note references: AUT-MOD, AUT-NOTE
- CFG ambiguity
AUT19
Simplification, CNF and membership
[Exam Focus]- Grammar simplification
- Null A→ε; unit A→B
- Mark nullable variables
- Omit nullable occurrences through alternatives
- Fresh start preserves ε
- Unit-chain reachability copies nonunit productions
- Remove nongenerating, then unreachable
- Nullable deletion: nonempty-word loss trap
👁 Full explanation
A null production is A→ε; a unit production is A→B with one variable. Mark nullable variables and add alternatives omitting nullable occurrences, preserving ε through a fresh start when needed. Remove unit rules by copying nonunit productions reachable through unit chains. Remove nongenerating variables, then unreachable symbols. Do not delete a nullable variable's every use and lose valid nonempty words. - CNF and CYK membership
- A→BC or A→a
- Optional isolated S₀→ε
- Long-rule terminals replaced by variables
- Binary variable-sequence splitting
- A→aBC ⇒ A→XC₁, X→a, C₁→BC
- CYK: substring variable sets
- Combine splits using A→BC
- Fixed grammar: O(n³)
- n>0: n terminal, n−1 binary rules
👁 Full explanation
Chomsky normal form uses A→BC or A→a, with an optional isolated S₀→ε. Replace terminals in long right sides by variables and split long variable sequences into binary steps: A→aBC becomes A→XC₁, X→a, C₁→BC. For CNF membership, CYK fills variables generating each substring, combining splits with A→BC. For a fixed grammar its time is O(n³); n>0 derivations contain n terminal rules and n−1 binary rules.
1 related practice question
Blueprint: LO3 · Note references: AUT-MOD, AUT-NOTE, AUT-CNF
- Grammar simplification
AUT20
Greibach form and left recursion
[Exam Focus]- Greibach normal form
- A→aA₁…Aₖ, k≥0
- Leading terminal, then only variables
- ε: isolated fresh start
- Fresh start absent from right sides
- Length n>0: n leftmost rule applications
- Each step adds one prefix terminal
👁 Full explanation
Greibach normal form requires A→aA₁…Aₖ, k≥0: one leading terminal followed only by variables. Handle ε separately through a fresh start that never appears on a right side. A nonempty word of length n takes exactly n leftmost rule applications because each contributes one terminal to the prefix. - GNF conversion choices
- Remove ε, unit, useless rules
- Order variables; substitute earlier-leading rules
- Remove left recursion
- Substitute until terminal-leading
- CNF-first: optional algorithm choice
- A→Aα|β ⇒ A→βR, R→αR|ε
- Further ε normalization
- No direct or indirect left recursion
- First-step question requires named algorithm
👁 Full explanation
A constructive route removes ε/unit/useless rules, orders variables, substitutes rules beginning with earlier variables, removes left recursion, and substitutes until every rule begins with a terminal. Some algorithms first convert to CNF; this is a method choice, not a universally mandatory first step. Direct A→Aα|β can become A→βR, R→αR|ε, then further normalization handles ε. GNF cannot retain direct or indirect left recursion. A question demanding the first step must name its chosen algorithm.
2 related practice questions
Blueprint: LO3 · Note references: AUT-MOD, AUT-GUIDE, AUT-GNF
- Greibach normal form
AUT21
PDA configuration and acceptance
[Exam Focus]- PDA structure and transitions
- (Q,Σ,Γ,δ,q₀,Z₀,F)
- Finite control plus stack
- State,input/ε,top → new-state,replacement pairs
- Stack-top orientation before traces
- X→X: unchanged stack
- ε input: no consumption
- X→ε: pop
- Distinct ε roles
👁 Full explanation
A nondeterministic pushdown automaton (PDA) adds a stack to finite control: (Q,Σ,Γ,δ,q₀,Z₀,F). Its transition relation maps (state,input symbol or ε,stack top) to possible (new state,replacement stack string) pairs. Fix which end denotes the top before tracing. Replacing X by X leaves the stack unchanged; ε input means consume no symbol, while replacing X by ε pops it. These are different uses of ε. - PDA configurations and acceptance
- State; unread input; stack
- Final-state mode: consumed input, final state
- Empty-stack mode: consumed input, empty stack
- NPDA modes: same language family
- Conversion, not same unmodified machine
- DPDA acceptance conventions need care
👁 Full explanation
A configuration records state, unread input and stack. Final-state acceptance requires all input consumed and a final state; empty-stack acceptance requires all input consumed and an empty stack. For NPDAs the modes characterize the same language family, through a construction, not necessarily the same unmodified machine. Deterministic-PDA acceptance conventions need extra care and are not automatically interchangeable.
9 related practice questions
Blueprint: LO1, LO3 · Note references: AUT-MOD, AUT-NOTE
- PDA structure and transitions
AUT22
PDA Construction and Determinism
[Exam Focus]- PDA for aⁿbⁿ
- Push X per a
- Switch to b phase
- Pop X per b
- End input at bottom marker
- Reject a after b phase
- Reject b without X
- Explicit ε handling for n=0
- Stack counting ≠ random-access input storage
👁 Full explanation
For aⁿbⁿ, push one X per a, switch to a b-reading phase, pop one X per b, and accept when input ends at the bottom marker. Reject a after entering the b phase and b when no X remains. Handle ε explicitly if n=0 is permitted. A stack counts without storing the full input as random-access memory. - Mirror versus copy and determinism
- wwᴿ: push, guess midpoint, match pops
- Binary unmarked midpoint: CFL, not DCFL
- wcwᴿ: visible switch, DPDA sufficient
- Unary even palindromes: even length, REG
- ww: same-forward-order copy
- Binary copy language ≠ palindrome language
- Single-stack comparison limitation
👁 Full explanation
For even palindromes wwᴿ over {a,b}, push the first half, nondeterministically guess its midpoint, then pop matching symbols. No center marker makes that language context-free but not deterministic context-free. With a marker wcwᴿ the switch point is visible and a DPDA suffices. Unary even palindromes are merely even-length words and regular. A PDA cannot compare two arbitrary halves in the same forward order: {ww:w∈{a,b}*} is the copy language, not the palindrome language.
6 related practice questions
Blueprint: LO2, LO3 · Note references: AUT-MOD, AUT-NOTE, AUT-PAL
- PDA for aⁿbⁿ
AUT23
CFL closure and counterexamples
[Exam Focus]- CFL closure with regular intersection
- Union; concatenation; star; reversal
- CFL∩REG: context-free
- PDA×DFA control; original stack
- Consumed symbol updates both states
- ε move leaves DFA unchanged
- Not necessarily regular
- aⁿbⁿ∩a*b*=aⁿbⁿ
👁 Full explanation
CFLs are closed under union, concatenation, star, reversal and intersection with a regular language. For CFL∩REG combine PDA control with DFA control, using the original stack; each consumed symbol updates both states, while an ε move leaves the DFA state unchanged. The result is guaranteed context-free, not necessarily regular: intersect aⁿbⁿ with a*b* to get aⁿbⁿ. - CFL nonclosure boundaries
- Arbitrary intersection not closed
- aⁿbⁿcᵐ and aᵐbⁿcⁿ: CFL
- Intersection aⁿbⁿcⁿ: non-CFL
- Complement/arbitrary difference not closed
- CFL−REG: CFL
- Intersect with regular complement
- Failed proposed PDA ≠ impossibility proof
👁 Full explanation
CFLs are not closed under arbitrary intersection. Both {aⁿbⁿcᵐ} and {aᵐbⁿcⁿ} are context-free; their intersection aⁿbⁿcⁿ is not. Nor are CFLs closed under complement or arbitrary difference. CFL minus a regular language remains CFL by intersecting with the regular complement. A failed construction of one proposed PDA proves only that construction fails, not that every PDA fails.
1 related practice question
Blueprint: LO2 · Note references: AUT-MOD, AUT-NOTE, AUT-CFL
- CFL closure with regular intersection
AUT24
CFL pumping proof and copy versus mirror
[Exam Focus]- CFL pumping lemma
- CFL assumption; some pumping length p
- Every sufficiently long s∈L
- s=uvxyz; |vxy|≤p; |vy|≥1
- ∀i≥0: uvⁱxyⁱz∈L
- v and y pumped together
- Either empty, not both
- Non-CFL proof: arbitrary pumping length
- Every allowed decomposition defeated
👁 Full explanation
If L is context-free, some p ensures each sufficiently long s∈L has s=uvxyz with |vxy|≤p, |vy|≥1 and uvⁱxyⁱz∈L for every i≥0. The two pieces v and y are pumped together; either may be empty, not both. A non-CFL proof must defeat every allowed decomposition. - Three-count and copy-language boundaries
- Witness aᵖbᵖcᵖ
- Window cannot contain a and c
- At most two blocks affected
- At least one count changes
- i=0 or 2
- Third count fixed or order broken
- aⁿbⁿcⁿ: non-CFL
- Binary ww: non-CFL
- wwᴿ grammar: S→aSa|bSb|ε
- Calling ww palindrome: contradictory
👁 Full explanation
For s=aᵖbᵖcᵖ, the window vxy cannot contain both an a and a c. Pumping affects at most two blocks and at least one count. Use i=0 or 2: the unaffected third block retains p while another count changes, or symbol order breaks. Hence aⁿbⁿcⁿ is not CFL. The copy language ww is also non-CFL over two symbols, whereas wwᴿ has the explicit grammar S→aSa|bSb|ε. An expression that writes ww and calls it a palindrome is contradictory.
3 related practice questions
Blueprint: LO2 · Note references: AUT-MOD, AUT-NOTE
- CFL pumping lemma
AUT25
Context-sensitive rules and linear bounded automata
[Exam Focus]- Context-sensitive and noncontracting rules
- αAβ→αγβ; γ≠ε
- Context-preserving variable replacement
- Complete-side length nondecrease
- Isolated ε exception
- Unrelated |β|≥|α| comparison trap
👁 Full explanation
A context-sensitive rule αAβ→αγβ replaces A in context, with γ nonempty. Equivalently, noncontracting grammar presentations preserve/increase total length, with the isolated ε exception. The condition is on the complete sides, not an unrelated comparison |β|≥|α|. - LBA and CSL decidability
- Length-n input: O(n) tape cells
- CSL ↔ nondeterministic LBA
- aⁿbⁿcⁿ: verify a*b*c* order
- Repeated one-a,b,c marking
- Missing/excess symbols rejected
- Marks confined to input region
- m cells: ≤|Q|m|Γ|ᵐ configurations
- Finite-graph acceptance reachability
- Looping branches allowed
- Every CSL decidable
👁 Full explanation
A linear bounded automaton (LBA) is a TM with O(n) tape cells on length-n input; the standard CSL characterization uses nondeterministic LBAs. For aⁿbⁿcⁿ first verify a*b*c* order, repeatedly mark one unmarked a, b and c, and reject missing/excess symbols. All marks stay within the input region. A fixed input has finitely many configurations, at most |Q|m|Γ|ᵐ for m cells. Reachability search in that finite graph decides acceptance, even if some machine branches loop. Thus every CSL is decidable.
11 related practice questions
Blueprint: LO1, LO2, LO3 · Note references: AUT-MOD, AUT-NOTE, AUT-LBA
- Context-sensitive and noncontracting rules
AUT26
Language Classification and Boundaries
[Exam Focus]- Language-family classification
- a*b* and aⁿb: REG
- aⁿbⁿ: CFL, nonregular
- Binary wwᴿ: CFL
- Binary ww: non-CFL
- Both mirror/copy: decidable
- aⁿbⁿcⁿ: CSL, non-CFL, decidable
- Finite languages: regular
- Stronger models recognize lower-family languages
👁 Full explanation
a*b* and {aⁿb:n≥0} are regular. aⁿbⁿ is CFL but not regular. Over a two-symbol alphabet, wwᴿ is CFL, ww is not CFL; both are decidable. aⁿbⁿcⁿ is CSL but not CFL, and therefore decidable. Every finite language is regular. A stronger grammar or TM can still recognize any of these lower-family languages. - Unary prime-length boundary
- {aᵖ:p prime}: nonregular
- Choose prime q>pumping length p
- Pump piece length k≥1
- Pump exponent q+1
- Length q(k+1): composite
- Unary CFL ⇒ regular
- Prime-length language: non-CFL
- Bounded-workspace divisor test: CSL
- Listed examples: none nonrecursive
👁 Full explanation
Unary prime length {aᵖ:p prime} is nonregular: choose prime q above pumping length p; if pump piece has length k≥1, using exponent q+1 gives length q(k+1), composite. Every unary CFL is regular, so this language is not CFL either. It is nevertheless context-sensitive: count the input in bounded workspace and test divisors. The balanced-three-count, prime-length, palindrome and aⁿb examples above are all recursive languages.
6 related practice questions
Blueprint: LO2 · Note references: AUT-MOD, AUT-NOTE, AUT-UNARY
- Language-family classification
AUT27
TM components, transitions and configurations
[Exam Focus]- Turing machine components
- M=(Q,Σ,Γ,δ,q₀,qaccept,qreject)
- Finite state/tape alphabets
- Σ⊆Γ; blank □∈Γ−Σ
- Module blank∉Γ: wrong
- Finite control; read/write head; unbounded tape
- Input: initial tape content
- Separate input organ/stack unnecessary
👁 Full explanation
For a Turing machine (TM), use M=(Q,Σ,Γ,δ,q₀,qaccept,qreject), with finite state/tape alphabets, Σ⊆Γ and blank □∈Γ−Σ. The blank symbol belongs to the tape alphabet Γ, not the input alphabet Σ. The standard machine has finite control, a read/write head and an unbounded tape. Input is initial tape content, not a separate hardware organ; no separate stack is required. - TM transitions and instantaneous descriptions
- δ(q,a)=(p,b,L)
- Read a, write b, left, state p
- Halting states: no moves
- ID u q av: scans a
- Left: u=u′c ⇒ u′ p cbv
- Right: ub p v
- Unused tape: show blank
- Diagram-specific state/transition conventions
👁 Full explanation
δ(q,a)=(p,b,L) means read a in q, write b, move one cell left and enter p. Accept/reject halting states have no further moves under this convention. In ID u q av the head scans a; the left-move successor, when u=u'c, is u' p cbv. For a right move it is ub p v, showing a blank if the head enters unused tape. State and transition names must follow the diagram's declared convention.
5 related practice questions
Blueprint: LO1, LO3 · Note references: AUT-MOD, AUT-NOTE
- Turing machine components
AUT28
TM Design, Variants and Limits
[Exam Focus]- TM decision design and halting
- aⁿbⁿcⁿ: mark triples, reset scans
- Verify no unmatched symbols
- Progress: additional marks each round
- Finite rounds
- ww: reject odd length
- Mark/counter midpoint
- Corresponding-half symbol comparison
- Writable tape beyond single-stack access
- Acceptance test and all-input halting proof
👁 Full explanation
To decide aⁿbⁿcⁿ, repeatedly mark matching triples, resetting the head between scans, then verify no unmatched symbol remains. Each round marks additional input cells, so finitely many rounds suffice. To decide ww, reject odd length, locate the midpoint using marks/counters, and compare corresponding symbols of the two halves; writable tape permits access a single stack lacks. State both the acceptance test and why every input halts. - TM variants and Church–Turing thesis
- Off-line: read-only input, read/write work
- Multitape; multihead; two-way-infinite tape
- Nondeterministic TM: same recognition power
- Different simulation costs
- Two unbounded stacks simulate tape
- Turing completeness: general TM simulation
- No polynomial-speed implication
- Finite runs need finite cells
- Effective procedures: Church–Turing thesis
- Not proved runtime theorem
👁 Full explanation
An off-line TM has a read-only input tape and separate read/write work tape. Multitape, multihead, two-way-infinite-tape and nondeterministic TMs have the same language-recognition power as standard TMs, though simulation costs differ. Two unbounded stacks can simulate a tape. Turing completeness means ability to simulate general TM computation, not polynomial speed or literally using infinitely many cells in a finite run. The Church–Turing thesis connects effective procedures to this formal model; it is not a proved runtime theorem.
8 related practice questions
Blueprint: LO3 · Note references: AUT-MOD, AUT-NOTE
- TM decision design and halting
AUT29
Deciders, recognizers and complements
[Exam Focus]- Deciders versus recognizers
- Decider: halts on every input
- Recursive = decidable
- Recognizer: members halt-accept
- Nonmembers: halt-reject or loop
- RE = recognizable = semidecidable
- Loop ≠ rejecting halt
- Undecidable may remain recognizable
👁 Full explanation
A decider halts on every input and accepts exactly its language; these languages are recursive/decidable. A recognizer must halt and accept every member, but on a nonmember may halt-reject or loop. Its languages are recursively enumerable (RE), Turing-recognizable or semidecidable. Looping is nonacceptance, not a rejecting halt. An undecidable language may still have a recognizer. - Complements and computable functions
- DECIDABLE ⊊ RE
- L and complement RE ⇒ decidable
- Dovetail recognizers until acceptance
- Decider complement: swap outcomes
- Recognizer final-state flipping fails on loops
- Total computable functions
- Recursive function ≠ recursive self-calls
- Partial functions undefined on nonhalting computations
👁 Full explanation
Every decidable language is RE, and the containment is strict. If L and its complement are both RE, simulate their recognizers in dovetailed steps until one accepts, obtaining a decider. Conversely complementing a decider works because it always halts. Flipping final states in an arbitrary recognizer fails to handle nonmembers that loop. Recursive function theory's total computable functions are not merely programs written with recursive self-calls; partial computable functions may be undefined where computation does not halt.
6 related practice questions
Blueprint: LO1, LO2 · Note references: AUT-MOD, AUT-NOTE
- Deciders versus recognizers
AUT30
Halting, diagonalization and Rice’s theorem
[Exam Focus]- HALT and diagonalization
- HALT={⟨M,w⟩:M halts on w}
- Recognizable: simulate, accept any halt
- Assume halting decider H
- D(x): loop if H(x,x) predicts halt
- Otherwise halt
- D on own description: contradiction
- HALT: RE, undecidable
- Complement HALT not RE
- Both recognizable would yield decider
👁 Full explanation
HALT={⟨M,w⟩:M halts on w} is recognizable: simulate and accept upon any halt. Suppose a decider H determines halting. Construct D(x) that loops if H(x,x) says halt, otherwise halts. Running D on its own description contradicts H in both cases. Thus HALT is undecidable and witnesses RE beyond DECIDABLE. Its complement is not RE, or both recognizers would yield a decider. - Rice’s theorem and limits
- Nontrivial recognized-language semantic property
- Some RE languages satisfy, others not
- Empty language; contains ε; ≥3 words
- Undecidable language properties
- State count: syntactic
- Symbol-writing: machine behavior
- Nonlanguage properties require separate proof
- Undecidable: no general decider
- Currently unknown algorithm ≠ undecidability
👁 Full explanation
Rice's theorem makes every nontrivial semantic property of a TM's recognized language undecidable. Nontrivial means some recognized languages have it and some do not. Empty language, contains ε and at least three accepted words qualify. Number of states and whether a particular symbol is written are machine-behavior/syntactic properties, not automatically language properties; prove such claims separately. Undecidable means no general decider exists, not merely no algorithm is currently known.
5 related practice questions
Blueprint: LO2 · Note references: AUT-MOD, AUT-NOTE
- HALT and diagonalization
AUT31
Decidable and Undecidable Questions
[Exam Focus]- Decidable automata/grammar questions
- DFA membership: simulation
- NFA membership: reachable sets
- FA emptiness: reachable final state
- DFA equivalence: product acceptance disagreement
- CFG membership: parsing/CYK
- CFG emptiness: generating-variable marking
- Halting procedures
- Arbitrary TM membership distinction
👁 Full explanation
DFA/NFA word membership is decidable by simulation or reachable state sets. FA emptiness is reachable-accepting-state search; DFA equivalence searches the product for an acceptance disagreement. CFG membership is decidable by parsing/CYK and emptiness by marking variables that can generate terminal strings. These procedures halt and are not the same as deciding arbitrary TM membership. - Undecidable questions and syntax scope
- TM acceptance: RE-complete, undecidable
- HALT: undecidable
- General CFG ambiguity/equivalence: undecidable
- Fixed CFG-word membership: decidable
- Two trees establish particular ambiguity
- No universal ambiguity decider follows
- FORTRAN: syntax versus semantics versus computation
- Language name alone insufficient
👁 Full explanation
TM acceptance on input is RE-complete and undecidable; HALT is undecidable. General CFG ambiguity and CFG equivalence are undecidable even though membership for a given CFG and word is decidable. A concrete grammar's two parse trees can establish that particular grammar is ambiguous; this does not give an algorithm deciding ambiguity for every grammar. FORTRAN/programming-language questions must distinguish CFG-style syntax, semantic restrictions and Turing-complete computation; a language's name alone does not choose one formal classification.
1 related practice question
Blueprint: LO2 · Note references: AUT-MOD, AUT-NOTE, AUT-DECIDE
- Decidable automata/grammar questions
AUT32
Computable reductions for undecidability
[Exam Focus]- Computable many-one reduction
- A≤mB: total computable f
- x∈A iff f(x)∈B
- B decider plus f decides A
- Known-undecidable A → target B
- B≤mA alone: no B-hardness proof
👁 Full explanation
A many-one reduction A≤mB is a total computable transformation f satisfying x∈A iff f(x)∈B. If B had a decider, compute f and invoke it to decide A. Therefore known-undecidable A reduced to B proves B undecidable. Showing B≤mA alone does not establish B's hardness. - HALT≤mA_TM construction
- Given ⟨M,w⟩, construct N
- N ignores input, simulates M(w)
- Accept on any M halt
- Rejecting halts included
- ⟨N,ε⟩ accepted iff M(w) halts
- Finite-description construction terminates
- Internal simulation may loop
- Both yes/no directions
- Computable mapping, not resemblance
👁 Full explanation
Example HALT≤mA_TM: given ⟨M,w⟩, construct N that ignores its input, simulates M(w), and accepts if M ever halts, including rejecting halts. Then ⟨N,ε⟩ is accepted iff M(w) halts. Construction of N's finite description terminates; the simulation inside N may not. Reductions require both yes and no directions and a computable mapping, not just a resemblance between two problems.
Blueprint: LO4 · Note references: AUT-MOD, AUT-NOTE, AUT-REDUCE
- Computable many-one reduction
AUT33
Resources and Input Encoding
[Exam Focus]- Resource measures and asymptotic bounds
- Time: computation steps
- Space: used cells/memory
- Read-only input inclusion convention
- Deterministic decider: length-n maximum
- Bounded NTM: every branch bounded
- Big-O: asymptotic upper bound
- Worst/average/best-case functions all eligible
- Θ: matching lower bound
👁 Full explanation
Time counts computation steps; space counts cells/memory used, specifying whether read-only input is excluded. For a deterministic decider use the maximum over all length-n inputs; for a time-bounded nondeterministic decider every branch meets the bound. Big-O is an asymptotic upper bound, not inherently a worst-case label: it can describe a worst-, average- or best-case function. Θ adds a matching lower bound. - Growth and encoding size
- 1 < log n < n
- n < n log n < n²
- n² < 2ⁿ < n!
- Fixed polynomial nᵏ versus exponential 2ⁿ
- Binary N: Θ(log N) bits
- O(N) not polynomial in binary length
- Pseudopolynomial: numeric magnitude dependence
- Huge polynomial degree: potentially impractical
👁 Full explanation
Growth typically orders 1,log n,n,n log n,n²,2ⁿ,n!. A fixed polynomial nᵏ differs from exponent 2ⁿ. Encoding matters: the number N in binary has Θ(log N) bits, so O(N) work is not polynomial in its binary input length. Pseudopolynomial algorithms depend on numeric magnitude rather than encoding length. A polynomial of enormous degree need not be practical.
3 related practice questions
Blueprint: LO4 · Note references: AUT-MOD, AUT-NOTE
- Resource measures and asymptotic bounds
AUT34
P, NP and polynomial verification
[Exam Focus]- P and NP definitions
- Classes of decision languages
- P: deterministic polynomial-time decider
- NP: nondeterministic polynomial-time decider
- Polynomial verifier and polynomial-size certificate
- Yes-input: some accepting certificate
- No-input: no accepting certificate
- NP ≠ non-polynomial
👁 Full explanation
Complexity classes here contain decision languages. P consists of deterministic polynomial-time decidable languages; NP consists of nondeterministic polynomial-time decidable languages, equivalently polynomially verifiable yes-instances with polynomial-size certificates. A verifier must accept some certificate exactly for yes-inputs; no certificate may falsely establish a no-instance. NP means nondeterministic polynomial, not non-polynomial. - CLIQUE verification and P⊆NP
- Certificate: k vertices
- Check distinctness and every pair-edge
- Polynomial in graph encoding
- P verifier ignores certificate
- P=NP: open
- NP ≠ definitely hard/outside P
- Finding/verifying intuition, not exponential-search necessity
👁 Full explanation
For CLIQUE, the certificate lists k vertices; verify they are distinct and every pair is an edge. This is polynomial in the graph encoding. P⊆NP because a verifier can ignore its certificate and run the P algorithm. P=NP remains open; NP does not mean definitely hard or definitely outside P. Finding versus verifying is an intuition for witnesses, not a rule that all NP instances need exponential search.
6 related practice questions
Blueprint: LO4 · Note references: AUT-MOD, AUT-NOTE, AUT-PNP, AUT-OPEN, AUT-BLUEPRINT
- P and NP definitions
AUT35
Polynomial Reductions and Consequences
[Exam Focus]- Polynomial reduction consequences
- A≤pB: polynomial f
- x∈A iff f(x)∈B
- Solving B solves A
- B at least A-hard
- B∈P ⇒ A∈P
- A NP-hard ⇒ B NP-hard
- A∈P ⇏ B∈P
- Same-class inference trap
- Polynomial reductions compose
👁 Full explanation
A≤pB means f is computable in polynomial time and x∈A iff f(x)∈B. Solving B then solves A, so B is at least as hard under this reduction. If B∈P then A∈P; if A is NP-hard then B is NP-hard. A∈P does not force B∈P, and the reduction alone does not place both problems in the same class. Polynomial reductions compose. - Hardness direction and mapping bounds
- Known-hard Y → new target X
- X→Y: reversed-proof trap
- Polynomial mapping time and instance size
- Undecidability: computable reduction sufficient
- NP-completeness: arbitrary computability insufficient
- Explicit reduction and resource bound
👁 Full explanation
To prove a new target X hard, reduce a known hard problem Y to X, not X to Y. The mapping and target instance must have polynomial size. For undecidability, general computable reductions suffice; for NP-completeness, an arbitrarily slow computable transformation is insufficient. Always state which reduction and resource bound are being used.
2 related practice questions
Blueprint: LO4 · Note references: AUT-MOD, AUT-NOTE
- Polynomial reduction consequences
AUT36
NP-Hardness, Completeness and Decision Formulations
[Exam Focus]- NP-hard versus NP-complete
- NP-hard: every NP language ≤pX
- NP-hard need not lie in NP
- NP-hard may be undecidable
- NP-complete: NP membership plus NP-hardness
- NP-complete lies inside NP
- Finite exhaustive certificates: exponential decision
- Multiple true source options
- Exponential necessity unproved
👁 Full explanation
X is NP-hard if every A∈NP satisfies A≤pX. It need not belong to NP and can even be undecidable. X is NP-complete if X∈NP and X is NP-hard. NP-complete languages lie inside NP and can be decided by finite exhaustive certificate search in exponential time. They are not known to require exponential time. - Canonical complexity examples
- SAT: satisfying Boolean assignment
- Cook–Levin: SAT NP-complete
- CNF-SAT and 3-SAT: NP-complete
- TSP decision: tour cost ≤B
- Standard finite encoding: NP-complete
- Shortest-tour optimization: NP-hard
- NP-complete requires decision formulation
- Fixed 2-colorability: P
- Fixed k≥3 colorability: NP-complete
👁 Full explanation
SAT asks whether a Boolean formula has a satisfying assignment; Cook–Levin establishes SAT NP-complete. CNF-SAT and 3-SAT are NP-complete versions. TSP decision asks whether a tour of cost at most B exists; it is NP-complete for standard finite encoded inputs. Finding the shortest tour is optimization and NP-hard; call it NP-complete only after specifying a decision formulation. Fixed 2-colorability is in P, while fixed k-colorability for k≥3 is NP-complete.
7 related practice questions
Blueprint: LO4 · Note references: AUT-MOD, AUT-NOTE
- NP-hard versus NP-complete
AUT37
3-SAT to CLIQUE Hardness Proof
[Exam Focus]- 3-SAT→CLIQUE construction
- CLIQUE∈NP: pairwise-edge certificate check
- m clauses
- Vertex per literal occurrence
- Edges: different clauses, noncomplementary literals
- Target clique size m
- Polynomial construction time and space
👁 Full explanation
First CLIQUE belongs to NP by the pairwise-edge certificate check. For a 3-CNF formula with m clauses, make one vertex for each literal occurrence. Connect two vertices iff they come from different clauses and are not complementary literals. Ask whether the graph has a clique of size m. Construction takes polynomial time and space. - 3-SAT→CLIQUE equivalence and correction
- Satisfying assignment: true literal per clause
- Consistent literals form clique
- m-clique: one occurrence per clause
- No complementary chosen literals
- Assign selected literals true
- Extend remaining variables arbitrarily
- Both implications
- Source formula: (x₁∨¬x₂)∧(¬x₁∨x₂∨x₃)∧¬x₃
- (true,true,false) satisfies all clauses
- ¬false=true: source correction
👁 Full explanation
A satisfying assignment supplies one true literal per clause; they are mutually consistent and form a clique. Conversely an m-clique selects one occurrence per clause, with no variable chosen both positively and negatively, so assign those literals true and extend remaining variables arbitrarily. Both implications prove equivalence. For (x₁∨¬x₂)∧(¬x₁∨x₂∨x₃)∧¬x₃, the assignment (true,true,false) satisfies all clauses because ¬false is true.
Blueprint: LO4 · Note references: AUT-MOD, AUT-NOTE, AUT-NPC
- 3-SAT→CLIQUE construction
AUT38
PSPACE, quantifiers and space reuse
[Exam Focus]- PSPACE and memory reuse
- PSPACE=⋃kSPACE(nᵏ)
- Deterministic polynomial workspace
- NP⊆PSPACE: enumerate/check witnesses sequentially
- Exponential candidates, reused memory
- Savitch: NSPACE(s)⊆DSPACE(s²)
- Appropriate s≥log n
- NPSPACE=PSPACE
- No P=NP implication
👁 Full explanation
PSPACE is ⋃kSPACE(nᵏ), using deterministic polynomial workspace. NP⊆PSPACE because candidate polynomial witnesses can be enumerated and checked one at a time, reusing memory; exponentially many candidates do not require retaining them all. Savitch's theorem gives NSPACE(s)⊆DSPACE(s²) for appropriate s≥log n, hence NPSPACE=PSPACE. It does not prove P=NP. - TQBF and quantifier evaluation
- Fully quantified Boolean truth
- TQBF: PSPACE-complete
- ∃x: either branch
- ∀x: both branches
- DFS assignments and recursion state
- Polynomial space, potentially exponential time
- ∀x∃y(x↔y): true
- ∃y∀x(x↔y): false
- Membership plus every-PSPACE-language hardness
- Stated reduction qualifier
👁 Full explanation
TQBF asks whether a fully quantified Boolean formula is true and is PSPACE-complete. Evaluate ∃x by trying one branch or the other; evaluate ∀x by requiring both. Depth-first evaluation stores assignments and recursion state using polynomial space despite potentially exponential time. For example ∀x∃y(x↔y) is true, but ∃y∀x(x↔y) is false. PSPACE-complete means membership plus hardness for every PSPACE language under the stated reduction.
2 related practice questions
Blueprint: LO4 · Note references: AUT-MOD, AUT-NOTE, AUT-SPACE, AUT-BLUEPRINT
- PSPACE and memory reuse
AUT39
Known Hierarchy and Open Separations
[Exam Focus]- Complexity containment hierarchy
- L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆EXPSPACE
- L/NL: logarithmic workspace
- EXPTIME=⋃kTIME(2^(nᵏ))
- Upper-bound class includes P
- Membership ≠ exponential necessity
- Hierarchy: P⊊EXPTIME
- Hierarchy: PSPACE⊊EXPSPACE
- Not all adjacent separations established
👁 Full explanation
Use L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆EXPSPACE. Here L/NL use logarithmic workspace; EXPTIME is ⋃kTIME(2^(nᵏ)), an upper-bound class that also contains P, not a statement that every member requires exponential time. Suitable hierarchy theorems prove P⊊EXPTIME and PSPACE⊊EXPSPACE. They do not establish every adjacent containment strictly. - Open separations and collapse limits
- P versus NP: open
- NP versus PSPACE: open
- PSPACE versus EXPTIME: open
- coNP: complements of NP languages
- P⊆NP∩coNP
- NP=coNP: open
- NP-complete in P ⇒ P=NP
- No all-decidable polynomial collapse
- Undecidable remains undecidable
- Cryptography/easiness claims require class and encoding
👁 Full explanation
P versus NP, NP versus PSPACE and PSPACE versus EXPTIME remain unresolved. coNP contains complements of NP languages; P⊆NP∩coNP, and NP=coNP is open. If any NP-complete language is in P, all NP collapses to P. This does not make every decidable language polynomial or make undecidable problems decidable. Avoid blanket claims about all cryptography or all problems becoming easy; the class and encoding matter.
5 related practice questions
Blueprint: LO4 · Note references: AUT-MOD, AUT-NOTE, AUT-HIERARCHY, AUT-BLUEPRINT
- Complexity containment hierarchy
AUT40
Unusual Bank Grammar Derivations
- Unusual right-linear grammar invariant
- S→11S|0A|1A; A→0|1|0S
- At most one rightmost variable
- Terminal word still sentential form
- S⇒11S⇒1111S⇒111111S⇒1111110A⇒11111101
- Return-to-S pairs: 11,00,10
- Prefix invariant over length guessing
👁 Full explanation
For S→11S|0A|1A and A→0|1|0S, every reachable form has at most one variable, at the right end. A complete terminal word is still a sentential form. For example S⇒11S⇒1111S⇒111111S⇒1111110A⇒11111101. Returning to S appends a pair 11,00 or 10; use that invariant to rule out impossible prefixes rather than guessing from string length. - Unusual grammar membership repair
- A→aB|bA|bBa; B→bB|cA|b
- Start variable required
- Assume start A
- Remove required a/b prefix
- Remove b…a wrapper
- B: match b, or recurse bB/cA
- Shorter residual guarantees termination
- All four offered words fail
- Marked choice contradicted; no option works
👁 Full explanation
For A→aB|bA|bBa and B→bB|cA|b, specify a start variable first. With A assumed, a terminating membership test recursively removes the required a/b prefix or b…a wrapper; B either matches b or removes b before B/c before A. Every recursive residual is shorter. Apply the membership test to every candidate word; none qualifies in this four-word example under the assumed start A. Use the membership test to justify whether a candidate word belongs to the language.
2 related practice questions
Note references: AUT-MOD, AUT-NOTE
- Unusual right-linear grammar invariant
AUT41
Source Defects and Missing Information
- Formula and diagram prerequisites
- Exact readable language and alphabet
- Arbitrary state labels
- Transition diagram and initial state
- Accepting markings or state meanings
- Theory alone cannot identify labels
👁 Full explanation
Use the exact readable language formula and alphabet when testing membership. State labels are arbitrary: use the transition diagram, initial state and accepting markings, or a definition assigning meanings to states. Language theory alone cannot identify an arbitrary state label. - Specific source defects
- Accepting start and ab-return paths
- Required ε and ab absent together
- Trace strings from the initial state
- Forward copy ww versus palindrome wwᴿ
- Capable/contains: least-family or exact-class qualifier
- Most difficult: reduction qualifier
- GNF first step: named algorithm
- Overlapping options: no invented unique key
👁 Full explanation
An accepting start state and an ab return cycle require a corresponding regular expression to include both ε and ab. Declare the start variable before testing grammar membership; with A assumed in the grammar above, none of the four candidate words qualifies. Distinguish the non-CFL copy language ww from the even-palindrome language wwᴿ. Generic capable, contains and most difficult questions need a least-family, exact-class or reduction qualifier. For GNF first-step questions identify the conversion algorithm. Evaluate each description against the stated language and machine conventions.
47 related practice questions
Note references: AUT-MOD, AUT-NOTE
- Formula and diagram prerequisites
No matching topics. Clear the search or change the filter.
Blueprint learning outcomes
- LO1 · Acquire insights into the relationship among formal languages, formal grammars, and automata
AUT01, AUT03, AUT04, AUT05, AUT06, AUT09, AUT13, AUT14, AUT16, AUT21, AUT25, AUT27, AUT29 - LO2 · Identify different formal language classes and their relationships
AUT05, AUT09, AUT14, AUT15, AUT17, AUT22, AUT23, AUT24, AUT25, AUT26, AUT29, AUT30, AUT31 - LO3 · Design grammars and recognizer for different formal languages
AUT07, AUT08, AUT10, AUT11, AUT13, AUT14, AUT17, AUT18, AUT19, AUT20, AUT21, AUT22, AUT25, AUT27, AUT28 - LO4 · Understand Complexity classes, P/NP/PSPACE, reductions, hardness, completeness, hierarchy, relationships between complexity classes
AUT32, AUT33, AUT34, AUT35, AUT36, AUT37, AUT38, AUT39