**CS402 Assignment No.2 Solution**

**Download File End post**

__Introduction to Computer Theory__

Summary

Introduction to the course title, Formal and In-formal
languages, Alphabets, Strings, Null string, Words, Valid and In-valid
alphabets, length of a string, Reverse of a string, Defining languages, Descriptive
definition of languages, EQUAL, EVEN-EVEN, INTEGER, EVEN, { a

^{n }b^{n}}, { a^{n }b^{n }a^{n }}, factorial, FACTORIAL, DOUBLEFACTORIAL, SQUARE, DOUBLESQUARE, PRIME, PALINDROME.__What does automata mean?__

It is the plural of automaton, and it means “something that works automatically”

__Introduction to languages__

There are two types of languages

Formal Languages (Syntactic
languages)

Informal Languages (Semantic
languages)

__Alphabets__

__Definition__

A finite non-empty set of symbols (called letters), is
called an alphabet. It is denoted by Σ ( Greek letter sigma).

__Example__

Σ = {a,b}

Σ =
{0,1} (important as this is the language
which the computer understands.)

Σ = {i,j,k}

__Note__Certain version of language ALGOL has 113 letters.

Σ (alphabet) includes letters, digits and a variety of
operators including sequential operators such as GOTO and IF

__Strings__

__Definition__

Concatenation of finite number of
letters from the alphabet is called a string.

__Example__

If Σ = {a,b} then

a, abab, aaabb,
ababababababababab

__Note__

__Empty string or null string__

Sometimes a string with no symbol at all is used, denoted by
(Small Greek letter Lambda) λ or (Capital Greek letter Lambda) Λ, is called an
empty string or null string.

The capital lambda will mostly be used to denote the empty
string, in further discussion.

__Words__

__Definition__

Words are strings belonging to some language.

__Example__

If Σ= {x} then a language L
can be defined as L={x

^{n }: n=1,2,3,…..} or L={x,xx,xxx,….}
Here x,xx,… are the words of L

__Note__

All words are strings, but not all strings are words.

__Valid/In-valid alphabets__

While defining an alphabet, an alphabet may contain letters
consisting of group of symbols for example Σ

_{1}= {B, aB, bab, d}.
Now consider an
alphabet

Σ

_{2}= {B, Ba, bab, d} and a string BababB.
This string can be tokenized in two different ways

(Ba), (bab), (B)

(B), (abab), (B)

Which shows that the second
group cannot be identified as a string, defined over Σ = {a, b}.

As when this string is scanned by the compiler (Lexical
Analyzer), first symbol B is identified as a letter belonging to Σ, while for
the second letter the lexical analyzer would not be able to identify, so while
defining an alphabet it should be kept in mind that ambiguity should not be
created.

__Remarks__

While defining an alphabet of letters consisting of more
than one symbols, no letter should be started with the letter of the same
alphabet i.e. one letter should not be the prefix of another. However, a letter
may be ended in a letter of same alphabet.

__Conclusion__

Σ

_{1}= {B, aB, bab, d}
Σ

_{2}= {B, Ba, bab, d}
Σ

_{1 }is a valid alphabet while Σ_{2 }is an in-valid alphabet.__Length of Strings__

__Definition__

The length of string s, denoted by |s|, is the number of
letters in the string.

__Example__Σ={a,b} s=ababa

|s|=5

_{ }__Example__

Σ= {B, aB, bab, d}

s=BaBbabBd

Tokenizing=(B), (aB), (bab), (B), (d)

|s|=5

__Reverse of a String__

__Definition__

The reverse of a string s denoted by Rev(s) or s

^{r}, is obtained by writing the letters of s in reverse order.__Example__

If s=abc is a string defined
over Σ={a,b,c} then Rev(s) or s

^{r }= cba__Example__

Σ= {B, aB, bab, d} s=BaBbabBd

Rev(s)=dBbabaBB

__Defining Languages__

The languages can be defined in different ways , such as
Descriptive definition, Recursive definition, using Regular Expressions(RE) and
using Finite Automaton(FA) etc.

__Descriptive definition of language__

The language is defined, describing the conditions imposed
on its words.

__Example__

The language L of
strings of odd length, defined over Σ={a}, can be written as

L={a, aaa, aaaaa,…..}

__Example__

The language L of strings that
does not start with a, defined over Σ ={a,b,c}, can be written as L
={L, b, c, ba, bb, bc, ca, cb, cc, …}

__Example__

The language L of strings of length 2, defined over Σ
={0,1,2}, can be written as

L={00, 01, 02,10, 11,12,20,21,22}

__Example__

The language L of strings ending in 0, defined over Σ ={0,1}, can be written as

L={0,00,10,000,010,100,110,…}

__Example__

The language EQUAL, of strings with number of a’s equal to
number of b’s, defined over Σ={a,b}, can be written as

{Λ ,ab,aabb,abab,baba,abba,…}

__Example__

The language EVEN-EVEN, of strings with even number of a’s
and even number of b’s, defined over Σ={a,b}, can be written as

{Λ, aa, bb, aaaa,aabb,abab, abba, baab, baba, bbaa, bbbb,…}

__Example__

The language INTEGER, of strings
defined over Σ={-,0,1,2,3,4,5,6,7,8,9}, can be written as INTEGER = {…,-2,-1,0,1,2,…}

__Example__

The language EVEN, of stings
defined over Σ={-,0,1,2,3,4,5,6,7,8,9}, can be written as EVEN = { …,-4,-2,0,2,4,…}

__Example__

The language {a

^{n}b^{n }}, of strings defined over Σ={a,b}, as
{a

^{n }b^{n }: n=1,2,3,…}, can be written as
{ab, aabb, aaabbb,aaaabbbb,…}

__Example__

The language {a

^{n}b^{n}a^{n }}, of strings defined over Σ={a,b}, as
{a

^{n }b^{n }a^{n}: n=1,2,3,…}, can be written as
{aba, aabbaa, aaabbbaaa,aaaabbbbaaaa,…}

__Example__

The language factorial, of strings defined over
Σ={0,1,2,3,4,5,6,7,8,9} i.e.

{1,2,6,24,120,…}

__Example__

The language FACTORIAL, of strings defined over Σ={a},
as

{a

^{n! }: n=1,2,3,…}, can be written as
{a,aa,aaaaaa,…}. It is to be noted that the language
FACTORIAL can be defined over any single letter alphabet.

__Example__

The language DOUBLEFACTORIAL, of strings defined over Σ={a,
b}, as

{a

^{n!}b^{n! }: n=1,2,3,…}, can be written as
{ab, aabb, aaaaaabbbbbb,…}

__Example__

The language SQUARE, of strings defined over Σ={a}, as

{a

^{n 2 }: n=1,2,3,…}, can be written as
{a, aaaa, aaaaaaaaa,…}

__Example__

The language DOUBLESQUARE, of strings defined over Σ={a,b},
as

{a

^{n 2 }b^{n 2 }: n=1,2,3,…}, can be written as
{ab, aaaabbbb, aaaaaaaaabbbbbbbbb,…}

__Example__

The language PRIME, of strings defined over Σ={a}, as

{a

^{p }: p is prime}, can be written as
{aa,aaa,aaaaa,aaaaaaa,aaaaaaaaaaa…}

__An Important language__

__PALINDROME__

The language consisting of Λ
and the strings s defined over Σ such
that Rev(s)=s. It is to be denoted that the words of PALINDROME are called
palindromes.

__Example__

For Σ={a,b},

PALINDROME={Λ , a, b, aa, bb, aaa, aba, bab, bbb, ...}

__Remark__

There are as many palindromes
of length 2n as there are of length 2n-1. To prove the above remark, the
following is to be noted:

__Note__

Number of strings of length ‘m’ defined over alphabet of ‘n’ letters is n

^{m}.__Examples__

The language of strings of
length 2, defined over Σ={a,b} is L={aa, ab, ba, bb} i.e. number of strings = 2

^{2 }The language of strings of length 3, defined over Σ={a,b} is L={aaa, aab, aba, baa, abb, bab, bba, bbb} i.e. number of strings = 2^{3}
To calculate the number of palindromes of length(2n), consider the following
diagram,

**Click Here To Download File**

## Post a Comment