cs402 theory of automata final 1st assignment solution fall 2010

[Xpert]

This solution can help you out just download it. have fun.

Objectives
Objective of this assignment is to make students able to understand the following concepts,
Recursive Definition of a language
Regular Expression
Finite Automata

Recursive Definition:
Question No.1
a. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings starting with a or
b
a. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings ending with aa.
b. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings NOT ending
with a.
c. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings NOT ending
with bb.
d. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings having aa at any
place.
e. Give recursive definition of language defined over alphabet Σ = {a, b}, having all strings NOT having aa
at any place.
_______________________________

Regular Expressions:
Question No.2

Give Regular Expression for each of the following language defined over alphabet Σ = {a, b}
b. Language having all strings STARTING with a or b
c. Language having all strings NOT having ab
d. Language having all strings NOT having bb
e. Language having all strings HAVING aa
f. Language having all strings HAVING bba
g. Language having all strings NOT having two consecutive a’s
h. Language having all strings NOT having even no of a’s and b’s
________________________________________

Finite Automaton:
Question No.3
Give Finite Automata for each of the following language defined over alphabet Σ = {a, b}
a. Language having all strings STARTING with a or b
b. Language having all strings NOT having ab
c. Language having all strings NOT having bb
d. Language having all strings HAVING aa
e. Language having all strings HAVING bba
f. Language having all strings NOT having two consecutive a’s
g. Language having all strings NOT having even no of a’s and b’s

_____________________________________

RE to FA and FA to RE conversion:
Question No.4

Convert FA’s of the following two languages you have already made in Question No.3 to RE’s using procedure
given in Kleene’s theorem and verify RE with your given RE in question 2.
a. Language having all strings HAVING aa
b. Language having all strings NOT having two consecutive a’s
___________________________

Important Note:
While attempting any question always remember the following points:
o Where OR is used in the description of a language it means that expressions on both sides of ‘OR’ are
parts of the language.
o Where NOT is used in 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).

Solution can be found on the attachment file.


[URL="http://www.vustudents.net/forum/topics/cs402-assignment01-solution?groupUrl=cs402theoryofautomata&xg_source=activity&id=3783342%3ATopic%3A291850&groupId=3783342%3AGroup%3A59504&page=4#comments#ixzz14lhAa3oC"]
[/URL]