Theory of Computation gives the mathematical foundation of languages, automata and computability. PSC questions often ask definitions of DFA/NFA/RE, construction, equivalence, closure and use of pumping lemma to prove non-regularity.

Engineering Definitions

Alphabet

Standard definition: A finite non-empty set of symbols.

Exam meaning: Language बनाउन प्रयोग हुने finite symbols set।

Language

Standard definition: A set of strings over an alphabet.

Exam meaning: Alphabet बाट बनेका strings को set।

DFA

Standard definition: A finite automaton with exactly one transition for each state-symbol pair.

Exam meaning: हरेक state-symbol मा exactly one next state भएको automaton।

NFA

Standard definition: A finite automaton that may have zero, one or many transitions for a state-symbol pair and may include epsilon moves.

Exam meaning: Multiple/epsilon choices हुन सक्ने finite automaton।

Regular expression

Standard definition: An algebraic notation for describing regular languages.

Exam meaning: Regular language describe गर्ने expression notation।

Concept Teaching

Regular languages can be represented equivalently by DFA, NFA and regular expressions. DFA is deterministic and directly executable. NFA is easier to design. Regular expression is compact notation. Pumping lemma proves certain languages are not regular.

DFA and NFA

Know the formal tuple and operational difference.

Model Transition behavior Acceptance
DFA Exactly one next state Single computation path ends in final state
NFA Many/zero/epsilon choices allowed Accepted if any path reaches final state
Epsilon-NFA Can move without consuming symbol Epsilon closure used in conversion

Regular Expression Operations

RE uses three core operations.

  • Union: R + S or R|S.
  • Concatenation: RS.
  • Kleene star: R* means zero or more repetitions.
  • Parentheses group subexpressions.
  • Every regular expression has equivalent finite automaton.
  • Every finite automaton has equivalent regular expression.

DFA Construction Concepts

Construction questions need state meaning.

  • Define what each state remembers.
  • Start state represents no input processed.
  • Final states satisfy language condition.
  • Trap/dead state handles invalid patterns.
  • Minimization merges equivalent states.
  • Product construction helps union/intersection/complement reasoning.

Pumping Lemma

Pumping lemma is used to prove a language is not regular.

  • If L is regular, every long enough string can be split xyz.
  • |xy| <= p and |y| > 0.
  • For all i >= 0, xy^i z must remain in L.
  • To prove non-regular, assume regular and choose a string that cannot be pumped.
  • Pumping lemma proves non-regularity, not regularity.

Engineering Mechanism

  • Define language condition.
  • Design automaton states based on required memory.
  • Set transitions for every input symbol.
  • Mark accepting states.
  • Convert NFA to DFA using subset construction when needed.
  • Use pumping lemma contradiction for non-regular languages.

Diagrams / Models To Draw

  • Draw DFA transition diagram.
  • Draw NFA with epsilon transition.
  • Draw subset construction table.
  • Draw regular expression to automaton idea.
  • Draw pumping lemma split xyz.

Formulas, Algorithms and Rules

  • DFA = (Q, Sigma, delta, q0, F).
  • NFA transition maps to subsets: delta: Q x Sigma -> P(Q).
  • Regular operations: union, concatenation, Kleene star.
  • Pumping lemma conditions: |xy| <= p, |y| > 0, xy^i z in L.
Concept Purpose Exam trap
DFA Deterministic recognition Must define all transitions
NFA Nondeterministic recognition Not more powerful than DFA
RE Language notation Equivalent to finite automata
Trap state Handles invalid input Often needed for complete DFA
Pumping lemma Prove non-regular Cannot prove regularity

Exam Point

  • DFA and NFA recognize same class: regular languages.
  • NFA may be easier but can be converted to DFA.
  • Pumping lemma is contradiction method.
  • State meaning matters in automaton construction.
  • Regular expressions are not programming regex features in exam theory context.

Worked Example

Language of binary strings ending in 01 can be recognized by DFA states remembering suffix progress: start/no match, seen 0, seen 01. Final state is seen 01, and transitions update the longest relevant suffix.

Subjective Answer Pattern

  • Define alphabet/language.
  • Explain DFA/NFA tuple and difference.
  • Explain regular expression equivalence.
  • Discuss construction/minimization basics.
  • Explain pumping lemma and limitation.

Common Engineering Mistakes

  • Saying NFA is more powerful than DFA for regular languages.
  • Leaving undefined DFA transitions.
  • Using pumping lemma to prove regularity.
  • Forgetting epsilon closure.
  • Not giving state meaning.

MCQ Revision

  • DFA tuple?
  • NFA accepts if how many paths reach final?
  • What does Kleene star mean?
  • Can every NFA convert to DFA?
  • Pumping lemma proves what?
  • What is trap state?

Final Summary

  • Regular languages are described by DFA, NFA and RE.
  • DFA is deterministic; NFA is nondeterministic but equivalent in power.
  • Automaton construction requires clear state meaning.
  • Pumping lemma proves non-regularity by contradiction.
  • TOC links language recognition and computation limits.