Bsc CSIT Semester 4 – Theory of Computation – Unit III: Regular Expressions (6 Hrs.)

(a) Strings whose second symbol from the right is 1 Let the alphabet be {0, 1}. If the second-from-right symbol is 1, the string must look like:   x 1 y where y is a single symbol (0 or 1) and x ∈ {

Question 4: Show that L = { 0^m 1^m | m ≥ 1 } is not a regular language Proof (by Pumping Lemma for Regular Languages): Assume, for contradiction, that L is regular. Then by the Pumping Lemma there ex

Regular Expressions for Languages over Alphabet {a, b} a. Set of all strings with substring 'bab' or 'abb' The language consists of any string that contains bab or abb as a contiguous part. The regul

Proof that $L = \{a^n \mid n \text{ is a prime number}\}$ is Not Regular We use the Pumping Lemma for Regular Languages to show by contradiction that $L$ is not a regular language. 1. Assume $L$ is Re

(a) Regular expression: \((0+1)^\,1\,0\,(1+0)\) - \(Q = \{q0, q1, q2, q3\}\) - \(\Sigma = \{0, 1\}\) - Start state: \(q0\) - Final state: \(F = \{q3\}\) Transition Function: - \(\delta(q0, 0)

(a) Regular Expression for strings over {a, b} having exactly two a’s and at least two b’s To have exactly two a’s, we place the two a’s in the string and the rest must be b’s. Also total number of

Proof (Pumping Lemma) that \(L=\{a^i b^j c^k \mid j = i + k\}\) is not regular 1. Pumping Lemma: If \(L\) is an infinite regular language then there exists a pumping length \(p\ge1\) such that eve

Kleene Closure vs Positive Closure (5 Marks) 1. Difference | Point | Kleene Closure (A\) | Positive Closure (A⁺) | |-----------|---------------------------|-----------------------------| | Meaning |

Construct Regular Expressions over {1,2,…,9} a) Strings of even numbers with length 4 starting with 2 and ending with 8 - Even digits = {2,4,6,8} - Length = 4 - Must start with 2 and end with 8