Theory of Automata
CS402
ASSIGNMENT NO.1
Total Marks= 20 (4+4+4+4+4)
Assignment Submission Deadline
Your assignment must be uploaded before or on 31-10-2011 [upload your assignment well before due date to avoid any assignment uploading related issues]
Rules for Marking
It should be clear that your assignment will not get any credit if:
o The assignment is submitted after due date
o The assignment is copied
Objectives
Objectives of this assignment are to make students able to understand the following concepts,
o Basic concepts clarification
o Recursive Definition of a language
o Regular Expression
o Finite Automata
Question No.1 Basic Concepts [Sets, Letters, Valid Alphabet, Languages, Strings and Words]
a. Which of the following are strings generated from alphabet Σ = {a, b}
i. abba
ii. baa$a
iii. abc.
iv. ba?
v. b.bba
b. Which of the following are valid words for language of all strings ending with bab defined for alphabet Σ = {a, c , bab}
i. acccba
ii. cccbaa
iii. cccbab
iv. babbb
v. baaab
Question No.2 Defining Languages [Using Recursive Definition, Re’s, Fa’s]
Give recursive definitions of following languages defined over alphabet Σ = {a, b}
i. Having all strings starting with b and having length greater than 2
ii. NOT having ab at any place.
Question No.3 Regular Expressions
Give Regular Expression for each of the following language defined over alphabet Σ = {a, b}
i. Even Length strings ending with b
ii. Strings with b’s count multiple of three
Question No.4 Models To Recognize Languages (Fa’s)
Give Finite Automata (FA) for each of the following language defined over alphabet Σ = {a, b}
i. Language having all strings NOT containing aa at any place
ii. Language of all strings NOT STARTING with bb
Question No.5 Models To Recognize Languages (Nfa’s)
Give Non Deterministic Finite Automata (NFA) for each of the following language defined over alphabet Σ = {a, b}
i. Language of all strings STARTING WITH bba
ii. Language having all strings NOT having even no of a’s and b’s
You can view the demo video in file,http://vulms.vu.edu.pk/Courses/CS402/Downloads/Assignment1.00.zipto see how to make FA in MS Word.
Note:
Please keep in view the following points while attempting any question:
• Where OR is used in the description of a language it means that expressions on both sides of ‘OR’ are parts of the language.
• Where NOT is used in the description of the language it means that language includes all strings except described in the ‘NOT’ condition, for example
language NOT starting with a, means all strings not having a in the start (you have to evaluate yourself what kinds of strings are these).
Assignment Uploading Instructions:
o Upload single word file having solutions for all parts as well as chart images.
o You can crop and compress images in the word file by double clicking on an image and selecting compress all images option to decrease file size before
uploading it.
Appendix:
Definition of Set:
A set can be defined as follows:
“Non repeating collection of elements”
Example Sets:
i. {car, bus }
ii. {table, chair , stand}
iii. {basket ,eggs}
iv. { ^, #, *, / }
However {car, car, bus} is NOT a set according to its definition.
Solution:
Question No.1 Basic Concepts [Sets, Letters, Valid Alphabet, Languages, Strings and Words]
a. Which of the following are strings generated from alphabet Σ = {a, b}
i. abba
ii. baa$a
iii. abc.
iv. ba?
v. b.bba
b. Which of the following are valid words for language of all strings ending with bab defined for alphabet Σ = {a, c , bab}
i. acccba
ii. cccbaa
iii. cccbab
iv. babbb
v. baaab
Question No.2 Defining Languages [Using Recursive Definition, Re’s, Fa’s]
Give recursive definitions of following languages defined over alphabet Σ = {a, b}
i. Having all strings starting with b and having length greater than 2
Answer. { baa, bab, bba, bbb, bba, baab, ….. .. }
ii. NOT having ab at any place.
Answer. {^, a, b, ba, bab, bba, bbb, baa, bbba,…..}
Question No.3 Regular Expressions
Give Regular Expression for each of the following language defined over alphabet Σ = {a, b}
i. Even Length strings ending with b
Answer. { ^ ,ab, bb, aabb,abab, bbbb, aaaabb, aaabab, ……}
ii. Strings with b’s count multiple of three
Answer. {^, bbb, bbbbbb, bbbbbbbbb, bbbbbbbbbbbb, bbbbbbbbbbbbbbb,
bbbbbbbbbbbbbbbbbb, bbbbbbbbbbbbbbbbbbbbb,………}
Question No.4 Models To Recognize Languages (Fa’s)
Give Finite Automata (FA) for each of the following language defined over alphabet Σ = {a, b}
i. Language having all strings NOT containing aa at any place
Answer. { ^, a, b, ab, ba, abb, bab,bba, baba, abbb, ….}
ii. Language of all strings NOT STARTING with bb
Answer. { ^, a, b, aab, aaab, abab, aabab, …….}
Question No.5 Models To Recognize Languages (Nfa’s)
Give Non Deterministic Finite Automata (NFA) for each of the following language defined over alphabet Σ = {a, b}
i. Language of all strings STARTING WITH bba
Answer. { ^, bba, bbaa, bbaba, bbaab, bbab, bbabb, …}
ii. Language having all strings NOT having even no of a’s and b’s
Answer. {^, a, b, aaab, bbba, ababab, aaaaab, bbbbba, ……}
