Scribd
Upload
72 views

automata and complexity theory AssignmentE

This assignment for Automata and Complexity Theory consists of various tasks including constructing a DFA from an NFA, finding regular expressions from transition diagrams, and building regular expressions and CFGs for specified languages. Students are required to work in groups of up to three, submit handwritten work by April 18, 2025, and participate in a questioning session upon submission. The assignment also includes applying the Pumping Lemma to prove certain languages are non-regular.

Uploaded by

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

automata and complexity theory AssignmentE

This assignment for Automata and Complexity Theory consists of various tasks including constructing a DFA from an NFA, finding regular expressions from transition diagrams, and building regular expressions and CFGs for specified languages. Students are required to work in groups of up to three, submit handwritten work by April 18, 2025, and participate in a questioning session upon submission. The assignment also includes applying the Pumping Lemma to prove certain languages are non-regular.

Uploaded by

Ahmed Tegegn
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Automata and Complexity Theory Assignment

Assignment (20pts)
Instructions:
• Be in a group of maximum of three members and work on the following questions.
• Don’t copy from each other and/or from other materials; provide your own solutions
accordingly.
• Any attempt of copying other’s work will result in the cancellation of your total mark.
• Submit the assignment in handwritten form.
• Deadline of your assignment work submission is on Friday April 18, 2025.
• During the submission of your work there will be a questioning-answering session
for each group member.
Questions:
1. Construct a DFA from the following NFA.

0 1,0

q 0
0
q1
0
1 1
q
0 3

q 0,1
2

0,1

2. For the following transition diagrams, find the corresponding regular expression.

Department of Computer Science Page 1


Automata and Complexity Theory Assignment

3. For the input alphabet ∑= {a, b} define a regular expression ‘r’ such that L(r) = {w є ∑* |
w has at least one pair of consecutive a} and perform the following operations.
a. Construct a NFA from the above regular expression using Thompson’s
Algorithm.
b. Convert the above NFA into its equivalent DFA
c. From the above DFA obtained in question b, reduce the number of states by
eliminating unnecessary states without affecting the language accepted.
4. For each of the following languages, build a regular expression.
a. L1={0k 1m2n | k,m,n≥1, 2k ≥ n}
b. L2={0n 1k 0n | k, n ≥1}
c. L3={anb2k ck | k, n ≥0}
d. L4={w | w contains at least two 1s, ∑= {a, b}}
e. L5={w | the length of w is even, ∑= {a, b}}
5. Construct a CFG for each of the languages described in question 4 and determine whether
each grammar is regular and/or linear grammars.
6. Understanding the Pumping Lemma:
a) State the Pumping Lemma for regular languages.
b) Explain the significance of the Pumping Lemma in classifying regular and non-regular
languages.
7. Applying the Pumping Lemma:
a) Use the Pumping Lemma to prove that the language L= {anbn ∣ n≥0} is not regular.
b) Show that the language L= {ap ∣ p is a prime number} is non-regular using the Pumping
Lemma.

Department of Computer Science Page 2

You might also like