CS402 Theory of Automata Assignment # 1 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, ……}