Theory of Computation · Unit 3 · 6 hrs
Regular Expressions
Exam-focused notes for Regular Expressions (Theory of Computation, CSC262): what the TU syllabus asks and how it has actually been tested, with 13 solved past questions from this unit.
What this unit covers
- Regular Expressions
- Regular Operators
- Regular Languages and their applications
- Algebraic Rules for Regular Expressions
- Equivalence of Regular Expression and Finite Automata
- Reduction of Regular Expression to ε – NFA
- Conversion of DFA to Regular Expression
- Properties of Regular Languages
- Pumping Lemma
- Application of Pumping Lemma
- Closure Properties of Regular Languages over (Union, Intersection, Complement)
- Minimization of Finite State Machines: Table Filling Algorithm
Minimization of Finite State Machines
List any two regular operators. Minimize the following finite state machine using Table Filling algorithm.[10]
--- Regular operators are the operations used to construct regular expressions from smaller ones. Any two of the following are acceptable: 1. Union ( or +): If $R$ and $S$ are regular expressions, then $R + S$ denotes the set of strings belonging to either ...
Full solved answer →Find the minimum state DFA for the given DFA below:
| States | 0 | 1 |
|---|---|---|
| A | B | F |
| B | E | C |
| C | B | D |
| *D | E | F |
| E | B | C |
| F | B | A |
[10]
Transition table: States 0 1 -------------- A B F B E C C B D D E F E B C F B A - Start state: A - Final state: D - Alphabet: {0, 1} - Final: {D} - Non-final: {A, B, C, E, F} Mark all pairs (X, D) for X in {A,B,C,E,F} as distinguishable: Marked: (A,D), (B,D...
Full solved answer →Regular Expressions
Write regular expression over {a,b} that represents a. Strings having exactly two a's and at least two b's. b. Strings having an even number of a's and each a followed by at least one b. [5]
- Alphabet: $\Sigma = \{a, b\}$ - Part (a): strings with exactly two a's AND at least two b's. - Part (b): strings with an even number of a's, and each a immediately followed by at least one b. --- Structure. With exactly two a's, every string has the shape...
Full solved answer →Give the regular expressions for the following language over alphabet {a, b}. a. Set of all strings with substring bab or abb. b. Set of all strings whose 3rd symbol is 'a' and 5th symbol is 'b'. [5]
We need all strings over {a, b} that contain bab as a substring, or contain abb as a substring (or both). Step-by-step reasoning: - Any string containing bab: prefix can be any string over {a,b}, then bab, then any suffix over {a,b} - RE: (a+b) bab (a+b) - ...
Full solved answer →Give the regular expressions for following language over alphabet {0, 1}. a. Set of all strings with 2nd symbol from right is 1. b. Set of all strings starting with 00 or 11 and ending with 10 or 01. [5]
Analysis: To ensure the 2nd symbol from the right is 1, the string must have the form: - The last symbol can be either 0 or 1, i.e., (0+1) - The 2nd from right must be 1 - Before that, there can be any string of 0s and 1s (including empty), i.e., (0+1) Regu...
Full solved answer →Construct regular expression over {1,2,...,9} that represents a. strings of even numbers with length 4 starting with 2 and ending with 8. b. strings starting with odd numbers and ending with even numbers. [5]
- Concatenation (.): places symbols/expressions one after another - Union (+): matches either expression - Kleene Star (): zero or more repetitions - Kleene Plus (+): one or more repetitions --- Constraints: - Length exactly 4 - First symbol: 2 - Last symbo...
Full solved answer →Pumping Lemma
Using pumping lemma, prove that the language is not regular. $L = {a^i b^j c^k \mid j=i+k}$ [5]
- Language: $L = \{a^i b^j c^k \mid j = i + k,\ i,k \ge 0\}$ - Alphabet: $\{a, b, c\}$ - Method required: Pumping Lemma for regular languages. --- Suppose $L$ is regular. Then by the Pumping Lemma, there exists a pumping length $p \ge 1$ such that any strin...
Full solved answer →State and prove the Pumping Lemma for regular languages. How can you show with example that pumping lemma is used to prove that a given language is not a regular? Explain.[10]
If A is a regular language, then there exists a pumping length 'p' such that any string 's' where s = p may be divided into three parts s = xyz, satisfying all of the following conditions: 1. xy^i z ∈ A for every i = 0 (the string can be "pumped" any number...
Full solved answer →Show that language is not a regular language. $L = { 0^m 1^m \mid m \geq 1 }$ [5]
--- If A is a regular language, then there exists a pumping length p such that any string s with s ≥ p can be divided into three parts s = xyz satisfying: 1. xy^i z ∈ A for every i ≥ 0 2. y 0 (y cannot be empty) 3. xy ≤ p (xy together must not exceed pumpin...
Full solved answer →Reduction of Regular Expression to ε – NFA
Convert the following regular expression into equivalent Finite Automata. a.(0+1)∗10(1+0)a. (0+1)10(1+0)a.(0+1)∗10(1+0)b.1∗0(0+1)∗1b. 10(0+1)*1b.1∗0(0+1)∗1[5]
Two regular expressions to convert to Finite Automata: - (a) $(0+1)^\,1\,0\,(1+0)$ - (b) $1^\,0\,(0+1)^\,1$ Alphabet: $\Sigma = \{0, 1\}$ for both. --- Break into parts: 1. $(0+1)^$ = any string of 0s and 1s (including empty) 2. $10$ = literal "10" 3. $(1+0...
Full solved answer →Define the NFA with ϵ−transition\epsilon-transitionϵ−transition and ϵ−closure\epsilon-closureϵ−closure of a state. Show that for every regular expression r, representing a language L, there is ϵ−NFA\epsilon-NFAϵ−NFA accepting the same language. Also convert regular expression (a+b)ab into equivalent Finite Automata.[10]
--- An NFA with ε-transition (also called ε-NFA) is a Nondeterministic Finite Automaton that allows transitions on the empty string ε (without consuming any input symbol). Formally, an ε-NFA is defined as a 5-tuple: M = (Q, Σ, δ, q₀, F) where: - Q = finite ...
Full solved answer →Application of Pumping Lemma
Show that L = {ana^nan | n is a prime number} is not a regular language. [5]
Note: The language can be simplified as L = {a^(3n) n is prime}, i.e., strings of a's whose length is 3 times a prime number. --- If A is a regular language, then there exists a pumping length p such that any string s in A with s = p can be written as s = x...
Full solved answer →Conversion of DFA to Regular Expression
State Arden's theorem. Convert following DFA into its regular expression using Arden theorem.
| 0 | 1 | |
|---|---|---|
| $\rightarrow *Q1$ | $Q1$ | $Q2$ |
| $Q2$ | $Q3$ | $Q2$ |
| $Q3$ | $Q1$ | $Q2$ |
[5]
Transition table: State 0 1 ------------- →Q1 Q1 Q2 Q2 Q3 Q2 Q3 Q1 Q2 - Start state: Q1 - Final state: Q1 If $P$ and $Q$ are regular expressions over $\Sigma$, and $P$ does not contain $\varepsilon$, then the equation $$R = Q + RP$$ has the unique solution ...
Full solved answer →Make Unit 3 stick
Practice CSC262 with flashcards & quizzes