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:
The assignment is submitted after due date
The assignment is copied
Objectives
Objectives of this assignment are to make students able to understand the following concepts,
Basic concepts clarification
Recursive Definition of a language
Regular Expression
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}
Having all strings starting with b and having length greater than 2
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}
Even Length strings ending with b
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}
Language having all strings NOT containing aa at any place
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}
Language of all strings STARTING WITH bba
Language having all strings NOT having even no of a’s and b’s
Solution will be Upload soon
