CS402 Assignment No. 1 Fall 2011 solution

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, ……}