Skip to main content

Reverse of a String and Defining Languages and PALINDROME

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 .

Comments

Popular posts from this blog

important question on Entity Relationship Model(ER Model)

5)A university registrar’s office maintains data about the following entities: (a) courses, including number, title, credits, syllabus, and prerequisites; (b) course offerings, including course number, year, semester, section number, instructor(s), timings, and classroom; (c) students, including student-id, name, and program; and (d) instructors, including identification number, name, department, and title. Further, the enrollment of students in courses and grades awarded to students in each course they are enrolled for must be appropriately modeled. Construct an E-R diagram for the registrar’s office. Document all assumptions that you make about the mapping constraints. Answer:   In the answer given here, the main entity sets are student, course, course-offering, and instructor. The entity set course-offering is a weak entity set dependent on course. The assumptions made are : a class meets only at one particular place and time. This E - R diagram cannot model a class meet

Library Management System DataFlow Diagram

Library Management System DataFlow Diagram 1) Zero Level DFD 2) 1st level DFD and 2nd level DFD

how to Install Numpy, Pandas and matplotlib on ubuntu 18.04 and Linux Mint

Install Python, NumPy,Matplotlib for Python 3 on Ubuntu 18.04, Linux Mint, Debian Linux. This is a short article about installing Numpy, Pandas , Matplotlib, Python3 on the latest Ubuntu 18.04 LTS, Linux Mint, Debian Linux which comes with Python 3.6.5. Let’s start by making sure we have an updated system: 1 sudo apt update 2 sudo apt upgrade Now, let’s install NumPy, Pandas,Matplotlib : sudo apt-get install python-pip sudo pip install numpy sudo pip install pandas sudo pip install matplotlib Test numpy : Open up a Terminal in Your Linux Operating System by running the following: python3 At the Terminal, type the following: >>> import numpy as np >>> np.__version__ '1.13.3'   Test Pandas : Open up a Terminal in Your Linux Operating System by running the following: python3 At the Terminal, type the following: >>> import pandas as pd >>> pd.__version__ '0.22.0'   Test Matpl