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, ...}
RemarkThere 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 .
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, ...}
RemarkThere 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 .
Comments
Post a Comment