Scribd
Upload
23 views3 pages

Final CS402 - Assignment - Spring2025 - Solution

The document presents an assignment for CS402 on the Theory of Automata, where the student is tasked with writing a regular expression for strings that start with 'a', contain 'ab', and end with 'b'. The regular expression provided is 'a(a|b)*ab(a|b)*b', and a corresponding Deterministic Finite Automaton (DFA) is designed to accept this language with specific states and transitions. The DFA ensures that the string starts with 'a', contains 'ab', and ends with 'b', with q3 as the only accepting state.

Uploaded by

Muhammad Umair
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
23 views3 pages

Final CS402 - Assignment - Spring2025 - Solution

The document presents an assignment for CS402 on the Theory of Automata, where the student is tasked with writing a regular expression for strings that start with 'a', contain 'ab', and end with 'b'. The regular expression provided is 'a(a|b)*ab(a|b)*b', and a corresponding Deterministic Finite Automaton (DFA) is designed to accept this language with specific states and transitions. The DFA ensures that the string starts with 'a', contains 'ab', and ends with 'b', with q3 as the only accepting state.

Uploaded by

Muhammad Umair
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

CS402 – Theory of Automata

Assignment # 01 – Spring 2025

Name:Muhammad Umair Sarwar

Student ID:Bc200407168

Question:
Write the regular expression for the language of all words starting with “a” and ending with
“b” and must contain “ab” as a substring, over the alphabet Σ = {a, b}.
Also draw the Finite Automaton (DFA) for the above language.

Solution:

1. Regular Expression
We are required to construct a regular expression for strings that satisfy all the following
conditions:
- The string begins with the character "a"
- The string must contain "ab" somewhere within
- The string ends with the character "b"

To meet these conditions, we develop the following expression:

a(a|b)*ab(a|b)*b

Explanation:
- The string starts with "a".
- "(a|b)*" allows any combination of a's and b's before and after the required "ab" substring.
- The "ab" ensures the condition of including "ab" explicitly.
- The final "b" guarantees that the string ends in "b".

This expression ensures all conditions are met while covering all possible valid
combinations.

2. Deterministic Finite Automaton (DFA)


To accept the language defined above, we design a DFA that tracks three essential
properties:
- Starting with an "a"
- Encountering "ab" as a substring
- Ensuring the string ends with a "b"

We define the following states:


- q0: Initial state (waiting for first character)
- q1: Read the first "a"
- q2: Detected "ab" somewhere in the string
- q3: Final state — only accepts strings that both contain "ab" and end with "b"

Transition Logic:

Current State Input Next State Meaning

q0 a q1 Starts correctly with


"a"

q1 a q1 Continue in initial
prefix

q1 b q2 Detected "ab"

q2 a q2 After "ab", keep


reading

q2 b q3 Ends in "b"

q3 a q2 Could lead to
another "ab"

q3 b q3 Remains valid if
more "b"s

Final State: q3 is the only accepting state.


DFA Diagram:

You might also like