Skip to content
CS Exit Ethiopia
Revision outline6 / 100 blueprint items

Automata and Complexity Theory

41 topics · 733 revision cues · 156 practice questions

0 / 41 topics reviewed
41 / 41 topics shown · Progress saved in this browser.
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.
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