Theory of Computation (CS C351) : BITS Pilani

Theory of Computation (CS C351)
BITS Pilani Dr.R.Gururaj

CS&IS Dept.
Hyderabad Campus
Alphabets and Languages
T1- Ch.1 ( Sections: 1.7 and 1.8)
1 CSC 351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus

Alphabets and Languages
Data is encoded in the computers memory as strings of bits or other symbols,

appropriate for manipulation by a computer.
We look at the mathematics of strings of symbols.
Alphabet
A finite set of symbols. Ex: Roman alphabet { a, b, c, d, ,z}
An alphabet pertinent to the computer is- Binary alphabet {0, 1}
An alphabet can be of any sort - { $, *, #}

String
A string over an alphabet is a finite sequence of symbols from the alphabet.
We use u, v, w, x, y, z, and Greek letters to denote strings.
Ex: elephant is a string over the roman alphabet {a, b, c, d, ,z}

00001110 is a string over the binary alphabet {0,1}
A string may contain no symbols and is called as an empty string or null string.
An empty denoted by e
We can also give name to string.

Ex: The string tiger may be named as w
The set of all strings including the empty string, over an alphabet is denoted by
*

The length of the string is its length as a sequence.
Length of tiger is 5
If the string tiger is named as w.
The length of the string w is represented by |w|= |tiger| = 5
and |e|=0
The value w(j) is jth symbol in the string w where j is between 1 and |w|
If the string tiger is named as w, then w(3)=g and w(5)=r

A string may contain a symbol that repeats at different positions.
We refer to them as different occurrences of the symbol.
Concatenation
Two strings over the same alphabet can be combined to form the third by the
operation of concatenation.
The concatenation of the strings x and y is written as x o y or simply xy
Formally, w= x o y if and only if |w|= |x|+|y|, w(j) = x(j) for j=1,|x|

and w(|x|+j)= y(j) for j=1,|y|.
Ex: tiger o cub = tigercub and 0110 o 110 = 0110110
Further w o e = e o w = w
Concatenation is associative.
(X0y)0z = X0(y0z)
A string v is a substring of w if and only if there are strings x and y
such that w=xvy
Both x and y could be e.
An empty string is substring of any string

A string is substring of itself
Suffix
If w=xv for some x, then v is a suffix of w
Prefix If w=vy for some y, then v is a prefix of w
For each string w and each natural number i, the string wi is defined as
w0=e, the empty string
wi+1=wi 0 w for i>= 0
Thus w1=w
come2 = comecome
The reversal of a string w is denoted by wR is the string spelled backwards.
Like how we represent infinite sets , the same format can be used to represent
infinite languages.
= {a, b, c}
* denotes all strings that can be formed using .
Hence a language is any set of strings over an alphabet that is any subset of *
Hence * , , and also are languages.

Most of the languages are infinite.
Ex: List all binary strings that are formed over {0, 1}
It is not possible.
We can represent by,
L= {w : w * }
The general form is L= {w : w * and w has property P }

List all the strings over {0, 1} that start with two zeroes and end with even no. of
ones.
Set of all integers that are divisible by 4. Ex: {4, 8, 12,}
If n is the no. symbols, and k is the length of the string, we can have nk
strings.
The infinite languages can be represented using set builder notation.

Since languages are sets we can apply set operations to them.
>Union, Intersection, Difference.
Another important operation is concatenation.
If L1 and L2 are languages the L = L1 L2 or simply L1L2
Where L= {w * : w = x y for some x L1 and y L2}
Ex: = {0, 1}
L1={w * : w has even number of zeros}
L2={w * : w starts with zero and rest are ones}
Now, L1 L2 = {w * : w has odd no. of zeros}
What is a Palindrome?
Kleene star of a language L is denoted by L*.
L* is the set of all strings obtained by concatenating zero or more strings from L.
Concatenating zero times is empty string.
BITS Pilani, Hyderabad Campus

Finite Representations of Languages
&
Regular Expressions

We use Regular Expressions as means of
representing certain subsets of strings over
Regular Expressions are used to describe languages
that consist of set of strings.
They describe languages exclusively by means of
single symbols and and *
They are useful for representing certain sets of string
in algebraic fashion.
Actually these describe the languages accepted by FA
We see U { (, ), U, , * } in Regular Expressions
Every regular expression represents a language

We give recursive definition of RE over as follows.
1. and each member of is a RE.
2. If and are REs then then so is ()
3. If and are REs then then so is ()
4. If is a REs then then so is *
5. Nothing is a RE unless it follows from (1) through
(4)
Regular expressions are precisely those obtained

recursively by application of rules 1-4 once or
several times.

The relationship between RE and Language
is established by a function L, such that if
is a RE the L() is a language represented
by .
That is L is a function from strings to
languages.

Theory of Computation (CS C351) : BITS Pilani

Uploaded by

Copyright:

Available Formats

Theory of Computation (CS C351) : BITS Pilani

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Theory of Computation (CS C351) : BITS Pilani

Uploaded by

Copyright:

Available Formats

Theory of Computation (CS C351)

BITS Pilani Dr.R.Gururaj

1 CSC 351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus

Data is encoded in the computers memory as strings of bits or other symbols,

We look at the mathematics of strings of symbols.

A finite set of symbols. Ex: Roman alphabet { a, b, c, d, ,z}

An alphabet pertinent to the computer is- Binary alphabet {0, 1}

An alphabet can be of any sort - { $, *, #}

2 CSC 351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus

We use u, v, w, x, y, z, and Greek letters to denote strings.

Ex: elephant is a string over the roman alphabet {a, b, c, d, ,z}

We can also give name to string.

3 CSC 351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus

If the string tiger is named as w.

The length of the string w is represented by |w|= |tiger| = 5

If the string tiger is named as w, then w(3)=g and w(5)=r

4 CSC 351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus

The concatenation of the strings x and y is written as x o y or simply xy

Formally, w= x o y if and only if |w|= |x|+|y|, w(j) = x(j) for j=1,|x|

Ex: tiger o cub = tigercub and 0110 o 110 = 0110110

Both x and y could be e.

An empty string is substring of any string

Prefix If w=vy for some y, then v is a prefix of w

* denotes all strings that can be formed using .

Hence * , , and also are languages.

7 CSC 351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus

We can represent by,

The general form is L= {w : w * and w has property P }

8 CSC 351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus

Set of all integers that are divisible by 4. Ex: {4, 8, 12,}

The infinite languages can be represented using set builder notation.

9 CSC 351 Theory of Computation Dr.R.Gururaj BITS Pilani, Hyderabad Campus

Another important operation is concatenation.

If L1 and L2 are languages the L = L1 L2 or simply L1L2

Where L= {w * : w = x y for some x L1 and y L2}

L1={w * : w has even number of zeros}

L2={w * : w starts with zero and rest are ones}

Now, L1 L2 = {w * : w has odd no. of zeros}

Concatenating zero times is empty string.

BITS Pilani, Hyderabad Campus

BITS Pilani, Hyderabad Campus

BITS Pilani, Hyderabad Campus

Regular expressions are precisely those obtained

BITS Pilani, Hyderabad Campus

BITS Pilani, Hyderabad Campus

You might also like