Q1. Strings vs Words
- String: Any combination of letters from an alphabet.
- Word: A string that follows the rules of a language.
Example: Alphabet Σ = {a, b} → strings: a, b, aa, ab …
Language: strings with only odd number of b’s → words: b, bbb, bbbbb …
Q2. Alphabet vs Element of a Set
- Alphabet is itself a set; its elements are letters.
- Example: Binary alphabet Σ = {0,1} → 0,1 are letters.
- Natural numbers N = {1,2,3,…} → elements are numbers.
Q3. Null String (Λ)
- String with zero symbols, denoted Λ (lambda).
Q4. Palindrome
- Strings equal to their reverse.
- Example: aa, aba, bbb, aabaa …
Q5. Valid/Invalid Alphabets
- Valid: No letter is a prefix of another.
- Example: Σ = {a, b, cd} ✅
- Invalid: Σ = {a, b, ac} ❌
Q6. ALGOL
- Early high-level programming language for scientific computation (ALGOL 58, 60, 68).
Q7. Sequential Operators
- a >> b → sequence (match a then b)
- a && b → sequential-and
- a || b → sequential-or
Q8. Determinism vs Non-Determinism
- Deterministic: Every input leads to a unique next state.
- Non-deterministic: Multiple possible next states; cannot directly implement on a computer.
Q9. Equivalent FA’s
- Accept the same language → equivalent.
Q10. Palindrome vs Reverse Function
- Palindrome: string equals its reverse.
- Reverse: spells a string backward.
Q11. Kleene Star (*)
- Σ* = all strings over Σ including Λ.
- Example: Σ = {x} → Σ* = {Λ, x, xx, xxx…}
Q12. Valid/Invalid Alphabets
- Already covered in Q5.
Q13. Reverse of a String
- Alphabet unchanged; only string is written backward.
Q14. Kleene Star vs Plus (+)
- Kleene Star: Σ* includes Λ.
- Plus: Σ+ excludes Λ.
Q15. Regular Expression (RE)
- Generalized form of language to generate strings.
- Example: L1 = {Λ, a, aa…} → a* ; L2 = {a, aa…} → a+