VU Past Papers – CS402 Solved Finite Automata and Transition Graphs Lectures 6–15

Q1. Finite Automaton (FA/FSM)

• Machine with finite states recognizing a regular language.

Q2–3. FA vs TG vs GTG

• FA: transitions labeled with single letters; deterministic.
• TG: transitions may be strings; allows null transitions.
• GTG: transitions can be regular expressions.

Q4. Union of FA’s

• FA1 ∪ FA2 accepts all strings accepted by FA1 or FA2.

Q6. Creating RE from a Language

• Finite: list all words separated by +
• Infinite: use *, + for patterns.
• Example: Strings starting with a → a(a+b)*

Q7–10. FA vs NFA

• FA: one transition per letter per state.
• NFA: multiple/no transitions possible per letter per state; all FA’s are NFA’s.

Q11. Understanding FA/NFA Traversal

• Start from initial state; follow transitions; accept if ends in final state.

---