D

Kavya.S
module-1 Theory of computation Asst. profevor
CSD, Dept
PESITM

uyh Define the following terms cuith an example

(i) Alphabet (ii) power of an alphabee (i) String
(Ev) String. concatenation (v) Language.

()Alphabet (Σ):
It is defined as a set of firite Syrokel
ex: E=0, 13 BEnary alphabet
E = {0,1,2,3----9} ser for dectonae
numbers.
2:

E {a,b,c,d --- 3 Alphabet set for

=
english alphabetic

(1?) power of an
0
alphabet (E*)
* 1

ex: 1) { = {0,2}
3= ser of string of lenger o1
= set of string of length 2

*= {0.1,00, 11,10,01,000,001,3
It Iz defined as set of strings of
all possible strings length derived
from E.
(i1i) StrEng (5):

symboly derived from aephabet (8

 wcgrr

ex: consider E=f0,23

that be derived pre
stringe
can

0,2,01 ☑ 001,101, 1002, 101010, --

(iv) String concatenation:

concatenationooff two strings (S11t) s

defined as string appending t to s
ex:= ab; Y=C

XY = abс.

() Language (L):
set
strings, all are. choosen from Σ!
of
0

where E. is a particlar alphabes Is

calledろう a
*
langiago.

ez: consider {=fa, 63

L1 = Sel of streng wtere rength is &dd
L1= $a, 6, aaa , 6bb, ababa,-- 99663
of string begio ith a and
L2. = Set d uuith ь
en

12 = 6 , abab6, aaab, aabaabb-.3

$aab

(VE) Symbol : It is a building block of

automata theory

CX: letter, number (0-g) etc

3

draw Automata:
Symbos to an

o
о 7 Enitial state
Trasition

Intermediate state

O End / final state

if called
special string. Stpt
E- epsilon: It is a
null string or em y string.
Streorg

Functions Relationgs
- substring
-Length
- cohcatenation -proper substoing
- Rephcation prefix, properprelie
_ Reversal - suffix raper
Sceffn 2

yLength: INumber of symbas In the given

Stoings
ex: 11011=3 1E/=0

of String: concatenation of
concaten ation
two
strings (s11t) is defined
S as string
appending t to s
ex X=ab, Y=c => xx = abc
=

3 Replication: Replication of string wis

defined os
w°=3
witl I w.w
u eg = a = aaa
(Repeating the occurance of w ?' no of tlmg
4) Replication: Replication ef string w is defirs

as w°sE

5) Reversal!
for each stoiong o defined as
is

() &f 11 =0 tnen wiw²=€ eg:(abс) сьа

Relations on e Strig
substring
& substring : A String 't is a

0 599 ,t' coneinvously ocoung in string

proper sabstring:
is proper suostoing of
577
A String
& a

.5 5J it is
оx: Eaabbae
аabbа
e, a, aa, a
ab,

roper substring

string is prefie of
prefex
,7, 993 A
ereht stsixes a

roper prefix:
A String s is a proper prefix of s Eff
String Is siffix of t and sft
oK: conider "abba"
,6,66,
e,6 bba, abba

proper suffüx
5

Function Ο on Language
All set operation etke union, ineeryecdion
complement be applied.
Difference and can

(2) concatenation of Language:

ex: L,= {aa, a63
72= 3 xх, уу 3
Ly2= faaxx, aayy, abxx, abYY 3

Set operation canguage

on

, v e n n e o f a's
L₁= {e, a, a4 a 6 - - - 3 l e
31odd ng of a's
L2 = { a', a, a5
operation
7IULE = {²or {a3a 11 union

$ or { 311 Entengection operation

n
/1 differenco operatio
1/ complement openation.

with neat
d s a g r
ds
a n i ,explnainAuatohi crauch y
mata theory
of лa nguage Oceasses Io
Regular Language (Fsm)
context free language(PDA
Decidable languagе (тт)
Semid e c i d a b l e . l a n g i a g e (some. Tm )

the tooly can be secected tased on

efficency: grasnS
2. computational
Fsm
6
Wsearly ion the length of Erput String
POA graes aae of eengeh of Enput
String
Tm gmous exponentially with length of
Erput String.
Semi-D-la
- sanguway
e
D language
CFL

Reqular
Language
PSM

PDA

TM

TM

2. Decidability?
FSM are decidable for example does Fsm
r strig
accepts some particular
IS Fsm is minimae ? Are &psm are
Edentical? PDA z also decidable. But
is

question wir.t fon can't be answered

3. clarity:
there are tooy to design Fsm anderery
requear language can alyo be deycribed
uhing reqular expression every eFL
recagnised by some pDA can be deserice
biyes grammer. No corresponding toor
exists fos the breader cearses of dircidkatle
& sem decidable лаnquages