1310 1948 PDF

Student Declaration
I Daniyal Akram Registration No. 18-ARID-369, hereby declare that I will not be involved
in any kind of cheating/copying/plagiarizing in solving the assignment based paper of Mid
Term Examination 2020. I take full responsibility of my conduct. If I found involved in any
kind of such activity of cheating/copying/plagiarizing then Institute reserves the right to take
any disciplinary action against me.
Student Signature
Mid Exam / spring 2020 (Paper Duration 24 hours)
To be filled by Teacher
Course No.: CS-536 Course Title: Theory of Automata and Formal

Languages
Total Marks: 18 Date of Exam: June 19, 2020
Degree: BSCS Semester: 4th and 5th Section: A & B
Marks
Q. No. 1 2 3 4 5 6 7 8 9 10 Obtained/
Total Marks
Marks
Obtained
Total Marks in Words: Eighteen
Name of the teacher: Yawar Abbas Abid
Who taught the course: Signature of teacher / Examiner:
To be filled by Student
Registration No.: 18-ARID-369 Name: Daniyal Akram
Answer the following questions.
Q.No.1.
a) What is the difference between FA, TG, and GTG? (Mark=01)
Answer:
FA:
● It stands for Finite Automata.
● It is a simple idealized machine used to recognize patterns.
● Example: Consider the language L of strings defined over Σ={a, b}, starting with b.
The L may be expressed by RE b(a + b)*, may be accepted by the following FA:
TG:
● It stands for Transition Graph.
● It is a collection of three things: a finite set of states, alphabet Σ of possible input
letters from which input strings are formed, and finite set of transitions.
● Example: Consider the Language L defined over Σ = {a, b} of all strings including Λ.
The language L may be accepted by the following TG:
GTG:
● It stands for Generalized Transition Graph.
● It is a transition graph whose edges are labeled with regular expressions or string of
input alphabets rest part of the graph is same as the usual transition graph.
● Example: Consider the language L of strings defined over Σ = {a,b}, containing double
a or double b. The language L can be expressed by the following regular expression
(a+b) * (aa + bb) (a+b)*. The language L may be accepted by the following GTG:
Difference:
Transition Graphs (TGs) and Generalized Transition Graphs (GTGs) provide some
relaxations. It is possible that there may exist more than one path or there may not be any
path for a certain string. This property is called non-determinism and can help in
differentiating FA, TG, and GTG from each other.
Hence, FA is also called a DFA. In GTG, directed edges connecting with some pair of states
are labeled with regular expression.
b) Determine RE corresponding to the following TG. Show all steps.
(Marks=02)
Answer:
Step No. 01: Eliminating states 7, 8, 10, and 11.
Step No. 02: Eliminating state 6.
Step No. 03: Eliminating states 9 and 12.
Step No. 04: Combining loops at state 3.

RE corresponding is ba(abba + aabb)*(b + Λ)ab
c) What is meant by non-determinism? Draw the TG for the following

RE (aa)*b(b*+( (aa)+b)*) bb (Marks=01)
Answer:
Non-Determinism:
Transition Graphs (TGs) and Generalized Transition Graphs (GTGs) provide some
relaxations. It is possible that there may exist more than one path or there may not be any
path for a certain string. This property is called non-determinism.
TG:
d) Draw an FA and also find the intersection of the following regular expressions
over the alphabet Σ = {0, 1} (Using De-Morgan's law)
(Marks=02)
RE.1 = (0+1) *00(0+1) *
RE.2 = (0+10*1) *
Answer:
Two regular languages RE.1 and RE.2 defined over the alphabet Σ = {a, b}, where:
Let,
RE.1 = (0+1) *00(0+1) * = (a+b)*aa(a+b)* = language with double a’s
RE.2 = (0+10*1) = (b+ab*a)* = containing even number of a’s
FAs accepting RE.1 and RE.2 is as below:
Now, FAs accepting RE.1 and RE.2:

(RE.1)
(RE.2)
New States after reading
Old States a b
z1+=(p,1) (q,2) = z4 (p,1) = z1
z2+= (p,2) (q,1) = z3 (p,2) = z2
z3+=(q,1) (r,2) = z6 (p,1) = z1
z4+=(q,2) (r,1) = z5 (p,2) = z2
z5=(r,1) (r,2) = z6 (r,1) = z5
z6+=(r,2) (r,1) = z5 (r,2) = z6
FA for RE.1c and RE.2c:
FA for (RE.1cRE.2c)c
Q.No.2.
a) Convert the following Non-Deterministic Finite Automata (NFA) to Deterministic
Finite Automata (DFA)
(Marks=1.5)
Answer:
b) Convert the following Non-Deterministic Finite Automata (NFA) to Deterministic
Finite Automata (DFA) (Marks=1.5)
Answer:
c) Convert the following NFA-˄ into FA. Draw Transition table corresponding to
required FA
(Marks=02)
Answer:
Transition table for given NFA is:
δ 0 1 λ
1 Ø Ø 2,6
2 Ø 3 Ø
3 Ø Ø 4
4 5 Ø Ø
5 Ø Ø 2,6
6 Ø Ø Ø
Transition corresponding is:

δ 0 1 λ
1 Ø Ø 2,6
2 Ø 3 Ø
3 Ø Ø 4
4 5 Ø Ø
5 Ø Ø 2,6
Q.No.3.
a) NFA corresponding to the Closure of an FA (NFA Kaleen’s Theorem) (Marks=02)
Answer:
Required NFA is:
b) Write down the tuples of DFA and NFA (Marks=1.5)
Answer:
Tuples of DFA:
DFA is represented by following tuples:
1) 0 is the starting state.
2) is a finite set of states.
3) is a finite set of symbols.
4) is the transition function for input symbols.
5) is a subset of .
Tuples of NFA:
NFA is represented by following tuples:
1) is finite set of states.
2) is a finite set of inputs.
3) is the transition function.
4) 0 is the starting state.
5) is a finite state.
c) Design a DFA such that: L = {anbmcl | n,m,l ≥ 0} Given: Input alphabet, Σ={a, b, c}
(Marks=1.5)
Answer:
d) Write the regular expression for the language containing the string in which every 0 is
immediately followed by 11. (Marks=0.5)
Answer:
The regular expression is:
R. E. = 011 + 1 ∗
e) All strings in which the total number of a's is divisible by three (Marks=0.5)
Answer:
For example, aabaabbaba.
b∗ ab∗ ab∗ab∗ ∗
f) All strings that have an even number of a's and an odd number of b's. (Marks=0.5)
Answer:
∗
aa + bb + ab + ba aa + bb ∗ ab + ba
g) Construct a regular expression for all strings in which the letter b is never tripled. This means that
no word contains the substring bbb Marks=0.5)
λ + b + bb a + ab + abb
Answer:
∗
Words can be empty or start and end with either a or b.

A compulsory a is inserted between all repetitions of b.

1310 1948 PDF

Uploaded by

Copyright:

Available Formats

1310 1948 PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

1310 1948 PDF

Uploaded by

Copyright:

Available Formats

Student Declaration

in any kind of cheating/copying/plagiarizing in solving the assignment based paper of Mid

any disciplinary action against me.

Course No.: CS-536 Course Title: Theory of Automata and Formal

Registration No.: 18-ARID-369 Name: Daniyal Akram

Answer the following questions.

Step No. 02: Eliminating state 6.

Step No. 03: Eliminating states 9 and 12.

Step No. 04: Combining loops at state 3.

Step No. 06: Eliminating state 4.

Step No. 07: Eliminating state 3.

RE corresponding is ba(abba + aabb)*(b + Λ)ab

c) What is meant by non-determinism? Draw the TG for the following

Now, FAs accepting RE.1 and RE.2:

Transition corresponding is:

a) NFA corresponding to the Closure of an FA (NFA Kaleen’s Theorem) (Marks=02)

Words can be empty or start and end with either a or b.

You might also like