Building Regular Expressions - University Questions

 

1. Find a regular expression for the set of positive integers in traditional decimal notation.

Answer:


(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)(0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)*

2. Find a regular expression for L = { aⁿ, n ≥ 2 } ∪ { bⁿ, n ≥ 1 }.

Answer:


aa a* + b b*

3. List all strings of length four in L((aa + bb)*).
Answer:
The expression generates even-length strings made of aa and bb only.

Strings of length 4:
aaaa, aabb, bbaa, bbbb

4. How many strings of length eight are  there in L((aa + bb) )*
Answer:

Each unit is aa or bb, i.e., 2 characters per unit.

Length 8 → 4 such units → total combinations = 2⁴ = 16

16 strings

5. Which of the following strings are in L((aa + b) )*

  • (i) aabbbbaa 

  • (ii) abbbba

  • (iii) aaabbbaaa

Answer:
Only (i) is in the language.

6. Is L((aa + b)) the same as L((b + aa))?

Yes — order in union doesn't matter.

Answer:
✅ Yes, they define the same language.

7. Is L((0+ 1))* is  same as L(0*+1*))? give example

Step-by-Step Comparison

🔹 L(r₁) = L((1 + 0)*)

This is:

  • All strings over {0, 1}.

  • Includes any combination, in any order.

  • Examples: ε, 0, 1, 01, 10, 0011, 1010, etc.

✅ Accepts all binary strings (i.e., Σ* where Σ = {0, 1}).

🔹 L(r₂) = L(0* + 1*)

This is:

  • All strings of only 0s, like ε, 0, 00, ...

  • Or all strings of only 1s, like ε, 1, 11, ...

⛔ Does not include mixed strings like 01, 10, 1100, etc.

❌ Conclusion: Not Equivalent

  • L((1 + 0)*) includes all binary strings.

  • L(0* + 1*) includes only unary strings (only 0s or only 1s).

Example to show they differ:

  • String "01" ∈ L((1 + 0)*) ✅

  • String "01" ∉ L(0* + 1*) ❌

8. Prove that L(r₁ + r₂) = L(r₂ + r₁), but L(r₁r₂) ≠ L(r₂r₁) in general.

Answer:

  • Union is commutative: r₁ + r₂ = r₂ + r₁

  • Concatenation is not: ab ≠ ba

Example:

  • r₁ = a, r₂ = b

  • L(r₁r₂) = ab

  • L(r₂r₁) = ba

So:
L(r₁ + r₂) = L(r₂ + r₁)
L(r₁r₂) ≠ L(r₂r₁)

More Questions

1. Q: Strings over {0,1} that contain exactly one 1

A: 0*1 0*
Explanation: Any number of 0s before and after exactly one 1.

2. Q: Strings over {a, b} that start and end with the same symbol

A: (a(a + b)*a) + (b(a + b)*b) + a + b
Explanation: Starts and ends with a or b, including length-1 strings.

✅ Explanation:

  • a(a + b)*a: Strings that start and end with a, with any sequence of a or b in between (including empty).

  • b(a + b)*b: Strings that start and end with b, similarly.

  • a + b: To include length-1 strings like a or b.

3. Q: Strings over {0,1} where every 0 is immediately followed by 1

A: (1 + 01)*
Explanation: Only 1s or 0s followed by 1.

4. Q: Strings over {a, b} with an even number of a's

A: ((b*ab*a)*b*)*
Explanation: Pairs of a's surrounded by any number of b's.

✅ Explanation:

Let’s break it down:

  • b* → Any number of bs before the first a.

  • ab*ab* → A pair of as, possibly separated by bs.

  • * on the outer group → Repeats of these pairs ensure even count of as.

Each ab*ab* contributes two as, ensuring the total number is even.

🔁 Examples of accepted strings:

  • "" → empty string (0 a's → even ✅)

  • bbbbb → no a's → even ✅

  • bababb → two as → even ✅

  • baababbbab → four as → even ✅

❌ Examples of rejected strings:

  • a → one a → odd ❌

  • abba → two as but not following the pattern of ab*ab* ❌

  • ababa → three as ❌

5. Q: Strings over {0,1} that do not contain 11

A: (0 + 10)*1?

To construct a regular expression for strings over {0,1} that do not contain the substring 11, we must allow any sequence of 0s and isolated 1s, but never two 1’s in a row.

✅ Regular Expression:

(0 + 10)* (1)?

✅ Explanation:

  • (0 + 10)*:

    • Allows:

      • 0 → a standalone 0.

      • 10 → a 1 that is not followed by another 1 (since 1 is followed by 0).

  • (1)?:

    • Optionally allows a single 1 at the end.

This ensures no two consecutive 1s can appear in the string.

✅ Examples of accepted strings:

  • "" (empty string)

  • 0, 1, 010, 1010, 01010

  • 000100010 ✅ (no 11)

❌ Examples of rejected strings:

  • 11

  • 0110 (contains 11)

  • 1011 (contains 11)

6. Q: Strings over {a, b} that contain at least one a and end in b

A: (a + b)*a(a + b)*b
Explanation: Ensure at least one a and ending in b.

7. Q: Strings over {0,1} that begin with 10

A: 10(0 + 1)*
Explanation: Fixed prefix followed by any string.

8. Q: Strings over {a, b} where a appears at least twice

A: (a + b)*a(a + b)*a(a + b)*
Explanation: Two or more as anywhere.

9. Q: Binary numbers divisible by 4 (i.e., ending in 00)

A: (0 + 1)*00
Explanation: Binary numbers ending with two 0s.

10. Q: Strings over {x, y} that do not contain yy

A: (x + yx)*y?

To build a regular expression for strings over the alphabet {x, y} that do not contain the substring yy, we must ensure that no two ys occur consecutively.

✅ Regular Expression:


(x + yx)* (y)?

✅ Explanation:

  • (x + yx)*:

    • Allows:

      • x: any number of xs.

      • yx: a y that is followed by an x, which prevents yy.

  • (y)?:

    • Optionally allows a single y at the end, which is safe (not followed by another y).

Together, this regular expression generates all strings where y never appears twice in a row.

✅ Examples of accepted strings:

  • "" (empty string)

  • x, y, xy, xyx, xxyxxyx, yxyx, xxyx

❌ Examples of rejected strings:

  • yy

  • xyy

  • xyyx, xxyyyx

These contain yy as a substring.


Comments

Post a Comment

Popular posts from this blog

Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme

About Me Course Details and Syllabus Theory of Computation PCCST302 Model Question Paper and Answers Module-1 Foundations of Finite Automata Motivation-Computability Need for Mathematical Modelling and automata Introducing automata     on-off switch     coffee vending machine Alphabet, Strings, and Languages Formal Definition of Finite Automata Deterministic Finite Automata - DFA Dead state in DFA Categories of DFA      Category 1: Accept Only the Given Input      Category 2: Starts and ends with      Category 3: Contains substring      Category 4: Specific length     Category 5: Divisibility ( Binary Numbers) Examples  DFA( University Questions) DFA Implementation C Program Non Deterministic Finite Automata - NFA Epsilon NFA  (∈-NFA) Examples NFA( University Questions) Regular Languages Epsilon Closure of NFA Eliminating Epsilon Transitions from NFA Epsilon Free NFA to DFA Conversion -...
Read more

Formal Definition - Turing Machine

Image
  📘 Formal Definition - Turing Machine A Turing Machine is a nine-tuple M = ( Q , Σ , Γ , δ , B , ⊢ , s,t, r) M = (Q, \Sigma, \Gamma, \delta, s_0, B, ⊢, s_{acc}, s_{rej}) where: Q – a finite set of states (typically denoted r , s , t , ... ). Σ – the input alphabet , which does not contain the blank symbol B or the left-end marker ⊢ . Γ – the tape alphabet , satisfying Σ ⊆ Γ , B ∈ Γ , ⊢ ∈ Γ Σ ⊆ Γ, \quad B ∈ Γ, \quad ⊢ ∈ Γ Every cell of the tape contains one symbol from Γ. δ – the transition function δ : ( Q − { t,r } ) × Γ → Q × Γ × { L , R } δ : (Q - \{s_{acc}, s_{rej}\}) \times Γ \to Q \times Γ \times \{L, R\} Given the current state and the symbol under the tape head, the machine writes a symbol, moves Left (L) or Right (R), and enters a new state. s ∈ Q – the initial (start) state . B ∈ Γ – the blank symbol , representing the empty tape cell. ⊢ ∈ Γ – the left-end marker , which appears at the extreme left of the tape and is never overwritte...
Read more

Non deterministic Finite Automata NFA

Image
  🤖 Formal Definition of NFA An NFA (Nondeterministic Finite Automaton) is a theoretical machine used to recognize regular languages , like a DFA, but it allows multiple transitions for the same input or even no input at all (ε-transitions) . 📘 An NFA is defined as a 5-tuple : M = ( Q , Σ , δ , q 0 , F ) M = (Q, \Sigma, \delta, q_0, F) Where: Symbol Description Q Q A finite set of states Σ \Sigma A finite set called the input alphabet δ \delta The transition function : δ : Q × ( Σ ∪ { ε } ) → 2 Q \delta: Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^Q  (a set of states) q 0 q_0 ​ The initial state , q 0 ∈ Q q_0 \in Q F F The set of accepting states , F ⊆ Q F \subseteq Q 💡 Key Differences from DFA: DFA NFA Only one transition per input                Multiple transitions possible No ε-transitions                ε-transitions allowed Deterministic      ...
Read more