Lectures 16–20: Nondeterministic FA (NFA)
Q1. NFA Concept
- Current state + input → may have multiple next states.
- Transition function targets subsets of states.
Q2. Why NFA?
- Easier to design; can later convert to FA.
Q3. NFA for Closure of FA
- Add new start/final state for Λ; connect transitions carefully.
Q4. Union, Concatenation, Closure of FA
- Union: strings in FA1 or FA2
- Concatenation: first part FA1, second part FA2
- Closure (*): strings of FA1 including Λ
Lectures 21–25: Sequential Circuits and Machines
Q1. Moore & Mealy Machines
- Used in computing operations (increment, 1’s complement).
Q2. Sequential Circuit
- Memory component (flip-flop); state depends on input & past state.
- Output = function of current state & input.
Q3–4. Pumping Lemma I & II
- Both identify non-regular languages.
- PLII stricter → easier for symmetrical languages like palindromes.
Lectures 31–35: CFGs and Languages
Q1. Word vs Semiword
- Word: only terminals, e.g., abba
- Semiword: terminals + exactly one nonterminal at end, e.g., aaaaaB
Derivation Tree vs Total Tree
- Derivation: specific word
- Total: all words in the language
Language Closure
- Closed under an operation if result stays in same language
Productions
- Rules to convert nonterminals → terminals
FA Operations
- Concatenation: string1 from FA1 + string2 from FA2
- Intersection: strings accepted by both FA’s
- Union / Addition: same effect
Lectures 36–40: CFGs, Null/Nullable, PDA
Nullable vs Null Production
- Null production: Nonterminal → Λ
- Nullable production: Derivation can eventually produce Λ
- Method: delete null productions, add new derived productions
CFG for Infix/Postfix Expressions
- Possible using derivation trees
Push Down Automata (PDA)
- FA + memory (stack) → recognizes more complex languages
Push Down Stack vs Store
- No difference; both describe memory