CS402 assignment no 1 Spring 2011 Idea solution
Question No.1
RECURSIVE DEFINITION
a. Give recursive definition of language defined over alphabet Σ = {a,
b}, having all
strings STARTING WITH aa OR ENDING WITH bb
b. Give recursive definition of language defined over alphabet Σ = {a,
b}, having all
strings with length MULTIPLE OF 2
c. Give recursive definition of language defined over alphabet Σ = {a,
b}, having all
strings NOT ENDING with aa or bb
d. Give recursive definition of language defined over alphabet Σ = {a, b}, NOT
HAVING ab at any place.
e. Give recursive definition of ODD PALINDROME (PALINDROME WITH
ODD STRINGS ONLY) defined over alphabet Σ = {a, b}
Solution:
Recursive definition of languages
The following three steps are used in recursive definition
Some basic words are specified in the language.
Rules for constructing more words are defined in the language.
No strings except those constructed in above, are allowed to be in the language.
Examples
Defining language of INTEGER
Step 1: 1 is in INTEGER.
Step 2: If x is in INTEGER then x+1 and x-1 are also in INTEGER.
Step 3: No strings except those constructed in above, are allowed to
be in INTEGER.
Defining language of EVEN
Step 1: 2 is in EVEN.
Theory of Automata (CS402)
(c) Copyright Virtual University of Pakistan
11
Step 2: If x is in EVEN then x+2 and x-2 are also in EVEN.
Step 3: No strings except those constructed in above, are allowed to be in EVEN.
Defining the language factorial
Step 1: As 0!=1, so 1 is in factorial.
Step 2: n!=n*(n-1)! is in factorial.
Step 3: No strings except those constructed in above, are allowed to
be in factorial.
Defining the language PALINDROME, defined over Σ = {a,b}
Step 1: a and b are in PALINDROME
Step 2: if x is palindrome, then s(x)Rev(s) and xx will also be
palindrome, where s belongs to Σ*
Step 3: No strings except those constructed in above, are allowed to
be in palindrome
Defining the language {anbn }, n=1,2,3,... , of strings defined over Σ={a,b}
Step 1: ab is in {anbn}
Step 2: if x is in {anbn}, then axb is in {anbn}
Step 3: No strings except those constructed in above, are allowed to
be in {anbn}
Defining the language L, of strings ending in a , defined over Σ={a,b}
Step 1: a is in L
Step 2: if x is in L then s(x) is also in L, where s belongs to Σ*
Step 3: No strings except those constructed in above, are allowed to be in L
Defining the language L, of strings beginning and ending in same
letters , defined over Σ={a, b}
Step 1: a and b are in L
Step 2: (a)s(a) and (b)s(b) are also in L, where s belongs to Σ*
Step 3: No strings except those constructed in above, are allowed to be in L
Defining the language L, of strings containing aa or bb , defined over Σ={a, b}
Step 1: aa and bb are in L
Step 2: s(aa)s and s(bb)s are also in L, where s belongs to Σ*
Step 3: No strings except those constructed in above, are allowed to be in L
Defining the language L, of strings containing exactly one a, defined
over Σ={a, b}
Step 1: a is in L
Step 2: s(aa)s is also in L, where s belongs to b*
Step 3: No strings except those constructed in above, are allowed to be in L
Question No.2
REGAULAR EXPRESSIONS
Give Regular Expression for each of the following language defined
over alphabet Σ =
{a, b}
a. Language having all strings STARTING AND ENDING WITH ab
b. Language of strings NOT having bb OR aa at any place
c. Language of all strings NOT HAVING aab in start
d. Language of all strings NOT HAVING aab in end
e. Language of all strings HAVING count of b's multiple of 2 [No restriction on
count of a]
Solution:
Regular Expression
As discussed earlier that a* generates Λ, a, aa, aaa, ... and a+
generates a, aa, aaa, aaaa, ..., so the language L1
= {Λ, a, aa, aaa, ...} and L2 = {a, aa, aaa, aaaa, ...} can simply be
expressed by a* and a+, respectively.
a* and a+ are called the regular expressions (RE) for L1 and L2 respectively.
Note a+, aa* and a*a generate L2.
Recursive definition of Regular Expression(RE)
Step 1: Every letter of Σ including Λ is a regular expression.
Step 2: If r1 and r2 are regular expressions then
(r1)
r1 r2
r1 + r2 and
r1*
are also regular expressions.
Step 3: Nothing else is a regular expression.
Method 3 (Regular Expressions)
Consider the language L={Λ, x, xx, xxx,...} of strings, defined over Σ = {x}.
We can write this language as the Kleene star closure of alphabet Σ or
L=Σ*={x}* .
This language can also be expressed by the regular expression x*.
Similarly the language L={x, xx, xxx,...}, defined over Σ = {x}, can be
expressed by the regular expression x+.
Now consider another language L, consisting of all possible strings,
defined over Σ = {a, b}. This language can
also be expressed by the regular expression (a + b)*.
Now consider another language L, of strings having exactly one a,
defined over Σ = {a, b}, then it's regular
expression may be b*ab*.
Now consider another language L, of even length, defined over Σ = {a,
b}, then it's regular expression may be
((a+b)(a+b))*.
Now consider another language L, of odd length, defined over Σ = {a,
b}, then it's regular expression may be
(a+b)((a+b)(a+b))* or ((a+b)(a+b))*(a+b).
Remark
It may be noted that a language may be expressed by more than one
regular expression, while given a regular
expression there exist a unique language generated by that regular expression.
Example
Consider the language, defined over
Σ = {a , b} of words having at least one a, may be expressed by a
regular expression (a+b)*a(a+b)*.
Consider the language, defined over Σ = {a, b} of words having at
least one a and one b, may be expressed by a
regular expression (a+b)*a(a+b)*b(a+b)*+ (a+b)*b(a+b)*a(a+b)*.
Consider the language, defined over Σ ={a, b}, of words starting with
double a and ending in double b then its
regular expression may be aa(a+b)*bb
Consider the language, defined over Σ ={a, b} of words starting with a
and ending in b OR
starting with b and ending in a, then its regular expression may be
a(a+b)*b+b(a+b)*a
Theory of Automata (CS402)
(c) Copyright Virtual University of Pakistan
13
Regular expression of EVEN-EVEN language, Difference between a* + b*
and (a+b)*, Equivalent regular
expressions; sum, product and closure of regular expressions; regular
languages, finite languages are regular,
introduction to finite automaton, definition of FA, transition table,
transition diagram
An important example
The Language EVEN-EVEN
Language of strings, defined over Σ={a, b} having even number of a's
and even number of b's. i.e.
EVEN-EVEN = {Λ, aa, bb, aaaa,aabb,abab, abba, baab, baba, bbaa,
bbbb,...}, its regular expression can be
written as (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*
Note
It is important to be clear about the difference of the following
regular expressions
r1 = a*+b*
r2 = (a+b)*
Here r1 does not generate any string of concatenation of a and b,
while r2 generates such strings.
Equivalent Regular Expressions
Definition
Two regular expressions are said to be equivalent if they generate the
same language.
Example
Consider the following regular expressions
r1 = (a + b)* (aa + bb)
r2 = (a + b)*aa + ( a + b)*bb then both regular expressions define the
language of strings ending in aa or bb.
Note
If r1 = (aa + bb) and r2 = ( a + b) then
r1+r2 = (aa + bb) + (a + b)
r1r2 = (aa + bb) (a + b)
= (aaa + aab + bba + bbb)
(r1)* = (aa + bb)*
Question No.3
FINITE AUTOMATA
Give Finite Automata for each of the following language defined over
alphabet Σ = {a, b}
a. Language having all strings with alternating a's and b's , some
example strings
are ababab... or bababa...
b. Language having all strings NOT containing aa at any place
c. Language of all strings NOT STARTING with bb
d. Language of all strings STARTING WITH bba
e. Language having all strings NOT having even no of a's and b's
Solution:
