0% found this document useful (0 votes)
405 views60 pagesFLAT Lords Paper
Uploaded by
Priya RanaCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
405 views60 pagesFLAT Lords Paper
Uploaded by
Priya RanaCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
/ 60
|
Module
1
Introduction
Alphabet, languages and grammars, productions and derivation, Chomsky hierarchy of languages.
POINTS TO REMEMBER fé q
An alphabet is any finite, nonempty set of symbols, typically denoted by 5
A string is a finite sequence of symbols chosen from some alphabet.
The length of a string is defined as the number of position for symbol in the string,
Empty string is also called null string
The string having no symbol is called the empty or null string
The reverse of a string can be obtained by writing symbols in reverse order.
A string s if it appears with in another string w then s is called a substring of w.
A string obtained by removing zero or more trailing symbols from a string z is called
Prefix and a string obtained by removing zero or more leading symbols from a string z is
called suffix of a string
4 Palindrome is a string which is the same whether it is written forward or backward.
QUESTION-ANSWERS
Q1. Explain the following terms :
(2) Alphabet
(b) String
{c) Length of string
(4) Empty or null string
(e) Reverse string
(f) Substring
Ans. (a) Alphabet : An alphabet is any finite, nonempty set of symbols, typically denoted
yy
_ Most common alphabets include :
(i) The binary alphabet : » = {0,1}
RGRRORAR __ LORDS Formal Language & A s
: q af corn lngth rom that alphabet by using the exponential notion: We
ing isa fits sequence of symbols chosen from some alpha
Semeaeaue = stra over Fa alphabet; its members 0 and 1 are symbols.
b | then axyrpgstod is a string over Sb its members are stings (each one of length 1)
}O.are two stings over the binary alphabet. These stings have lengths
respectively. Tht is, 0011/= 4 and [11010] = 5
Let us assume u and v be two strings in 3". Now, Jet
ru ie. w= uv. Then, the string w is said to be obtained.
ive since for each u,v.w in 3°, u(v w) =(u vw
hhas an identity element A with respect to the binary
STAR (closure) (pT, May 2008) -
80 Alphabet : fis an alphabet, we can express the set ofl sae [ev denote the lengths of the strings uv,uv respectively. rome of sting isa property of a sting in which st
from right to lett. Otherwords, a palindrom,
‘writen forward or backward.
indrome Is even then it can be obtained by the concatenation Of st ‘What are the different types of grammars/languages? .
then WR = yx, and the even palindrome is xyyx. ge) Unrestricted or phase structure grammar. (Type 0 grammar) (for TMs)
Bounded Automata)
J grammar (7
on result of any string with € is the same string)
nerators. They co
a starting symbol
Is a Diagonalization language Ld?
jonalization language : The diagonalization language consists of all stings
TMM whose code is w does not accept when w is given as input
superset of another grammar as per
ihat properties of r.e. sets are recursively enumerable ? pee 9 pat
eo er types grammars.
Tanguage Haskine
ae ore Type S| Regular Regular gammars | Fine Sate | a
Lauro Languages Automata
What properties of re, sets are not r.0.? Lett-linear grammars
a Type? | Contexties | Contenitee Push down | a6 :
Z languages | grammars Automata
Tye T_ | Coniex-sensive] Confextsenaive Linear boundl”aPBrer
languages | grammars Automata
Type 0 | Recursive] Unrestricted Turing |-aay
Languages ‘Grammars Machines computable
Focus function
enumerabie
following properties languages
inment property) -
a 4 strict hierarchy. Regular lang
languages < recursive languages © ro
by
‘Turing machine ~redton it gies reverse rohinst
rangle E> E+
EOE+ECE+E'E
roperis of LRW) grammar
Every LA(k) grammar G is unambiguous.
Gan A gama hex a ceteinsicpushiown suo cea 6
IfPisadeterintc pushdown alomaton P then there exist an A(t) grammar
grammar G,
languages i a proper subclass ofthe class of coe
fre angages. The class of deterministic languages canbe dented by loys,
languages (Looe is closed undar
omplmenaon but not ur
n is accepted bya
delerinsic pushdown avomala an has pei prope
There is an algotam o decide whetor a gen conte
a gen natura number K
Prove that every Lk) orammar is unambiguous.
Ans. We know ta, iw & L(G) fr which wo cite
‘grammar is ambiguous.
Lelie ast io of tose doraons bo
XAW=> xOu = W
BW" uA = wy
‘hon by defen of LR) grammar
X=u, A=B, and Q=A.
‘So both (1) and (2) rules are same/ideniical, so every LA(k) grammar is unambiguous.
(PTW, May 2010)
ree grammar is Li
(PTU, May 2008)
3 most derivations eis hen
lain the closure properties of language classes.
‘Ans. Various properties of language are :
4. ach ofthe classes Lo, Los, Lc, Lvare closed under union.
srsedution
wr
yt dss Le, Lin a ed
ee crs in Len Led ude Tose
ee es Le, i aed nanan
Ny? (PTU, May 2015)
reads the input and converts strings in the
‘expression we can specly pattems to Lex so it can generale
‘sean and match sings in the input. Each pattem inthe input to lex
rammars for YACC are described using a variant of Backus Naur Form (BNF).
‘his technique, pioneered by John Backus and Peter Naur, was used to describe ALGOLEO,
[NBNF grammar can be used to express contex-ree languages. Most consttucts in modem
uages can be rept
from one state to another)
22. each of the production in a grammar has some variable on its RHS, what
2 (PTU, May 2016)
‘each production of a grammar has at most one
(PTU, Dec. 2016)
ibject used in the generation of strings. A
sed in the generation of sting, A non- {erminal symbol willbe constructed from the terminal symbols; the number of term,
0 24. Explain the difference between the Top down parsing and g
Parsing. ‘ Neva
Ans. Botiom vp parsing: Tha approach isnt unde soting « OTE: MAY 2098
stan at the bottom of the parse tree with individual characters. We thor sat
‘connect the characters together into larger tokens as we go. At the end
S and S should be th
‘combining tokens in difer
fe sean so far. At each, step we st
feduce as far as possible by combining charact
Eg, String is acdaf
Parse tree
Top Down parsing : For this approach we assume that the string matches $ and look at
Tra peniomnaloynbo| may vary ks ee Caled a varene al smog
‘must be true, But (
‘as necessaty to prove the basic assertion
@.25. Find'the grammar generating L = {anbrcin = 1,120}. (PTU, Dec. 2016)
{Ans. The language consists of two parts.
@ 26, Reduce the given grammar into Chomsky Normal Form.
> abSb [a aAb.
‘A> bS [aAAb (PTU, May 2018)
Ans. S—>ZW lal KY
AS YSIKL
Loay
K>XA
wosy
Z>xY
X50
Yoo
@ 27. Write short note on Syntax Analysis. (PTU, Dec. 2016)
‘Ans, Syntax Analysis : Syntax analysis is also known as parsing or hierarchical analysis. oe
(CNF and GNF productions.
tween injective and Surjective function in a set.
between injective and Surject 4 one,
‘A tunction is caled one to one
grammar in GNF equiva mmmar E> Es TTT +14
P (TU, Dee. 2
Remove unis
Remove €>T, add ©» TRIE
= Remove EF add E>
= Remove T-» F add 7 (Eid
resus
ha)
is one-o-one using quanitios as
ET, TIME IT (ET)
FIT (ET)lid function.
The function { may map one or more
in B has a corresponding element a
oa Regular Language, 5
Finite Automate
Regular expressions and languages, deterministé fiite automata (DFA) and equivalence win
regular expressions, no ti 18 with OFA, requ
Properties of regular languages, pump
mata,
POINTS TO REMEMBER
© A regular expression is a string that describes the whole sot of
‘certain syntax rules
"A grammar is called linear in which at most one non-tormi
‘of any production,
4 Aight linear and lett inear are the types of linear grammar,
5 Pumping lemma is used to check if a language is regu
co
According tp
imal can occur on the right side
or not.
The regular expression have some permitted operators that can be used to build a
regular expression. These operators are
‘The regular sets are closed under union, concatenation and Kleene closure.
EE Thote are two properties of regular languages. These are
4. Decision property
2. Closure property
5 An aulomaton is an abstract model of a digital computer.
"= ‘There are two types of automaton. These are
1. Deterministic automata.
2, Non-deterministic automata.
-_ & Finite automaton consists of a finte set of states and a sot
© state that occur on input symbols chosen from an alphabet
1“
transitions from stato to
ges & Fite Automata
a is a directed graph in which the vertices:
‘of the graph correspond 10
of FA on
read contro! and fine control are the components of F/
xis accepted by a finite automaton
DFA can not use empty
NFA can use emply string
(PTU, May 2019, 2017)
expression is a string that describes the whole
Jes. These expressions are used by many text
tain patterns etc, 2
ression over © and the sets they denote are :
1d denotes the set {a}
noting the languages Rand S respectively then (rv).(rs) and
RS and A* respectively.
rammars.
ymmar G=(V;T,P.S) is defined as follows
rnon-terminals. S is the start symbol in V.
led terminals that form the strings of the language
T= 2),
‘set of symbols
‘generated by the gramme
AaB, where A.B < Vand a € T, or
A aywhere Ac Vanda T.
inear grammar ? Also discuss its types. (PTU, Dec. 2019)
fammar : A grammar is called linear in which at most on non-terminal
Fit near Lefties 8140 of any.
rightmost of temas
3 this grammar will have four stalos :S, A, B
stato.
S-+0Aand S +18 Jenaton (or ot)
| and Fare regular expressions, thon Fs (alzo wren as
) concatenated with L(R2).
Rj fsa regula expression, thon R,*(the Kieone closure of Ry) is
‘closure has the highest
}o{(0+4)"(00+11)],
the language which accepts all,
U(R1) O L(RIR) J LIRIRIAY) v..
“concatenation, followed by union.
(bse) 7
the language over the set 3.= (a,b) In
‘of two languages R, and Rz denoted by AUR, is tho set of
‘or Ro both.
i
|= (ab) and R= (abe) then
‘concatenation of two languages R, and R denoted by Ry.Az
can be formed by taking any string in R, and concatenating
b) and Fa = (64) then “
i) Odd length of string.
Ans. () Even length of sing R= (11° .
(li) Odd length of the string R= 1(11)" ig
closure) of a language R, is denoted by Ri" and
‘ean be formed by taking any number of strings from
he stings).
es LORDY Theor of Copan,
a
Q 19. Reg exp for :
18 over {0,1} with the substring ‘0101".
(i) All strings beginning with '11" and ending with ‘ab’.
‘with 3 consecutive b's
4 and has no substring ‘00’
losure property of regul 2
‘Ans. The regular sets are closed under union, concatenation and Klesne closure
ur
A=
The class of regular sets are closed under complementation, substitution, homomorphism
land inverse homomorphism.
@ 22. Reg exp for the language such that every string will have atleast one ‘a’
followed by one
The regular expressions F is given as
R=Q+RP
Which has a unique solution as R = QP*
ite down the identities for regular expressions.
expressions : Two regular expressions P and Q are
P and Q represent same set
impfying regular expressions,
1, G+RER
2. OR=RO=2
e*=eandO'=6
RAR =A
epuartanguages & Finite Avomata
42, (P+Q)R = PRGA and
26. Prove (1400°1)+(
‘or1(0+10"1)" (PTU, Dec. 2009)
Lis a regular language, prove that L, = (uv: u ¢ L,|v|=2) is also regul
(PTU, Dec. 21
=2) Then Lg is regular since it can be denoted by the regular
the alphabet is © = (cj4¢2.~1.--.Gn) then the regular expression © is
‘46,). Now note that Ly = L Lg, Since w € Ly if
ince both L and Lia are
eatenation, we conclude
‘Ans. Let La=(
expression ES. He
ised as shorthand to denote (6,+az4
cl and \V=2 iff weuv with uel and v © Lait € LL
regular languages are closed under
regular end we know t
the L; is regular
properties of regular languages.
(PTU, May 2019 ; Dec. 2019, 2018)
property
n property : This property gives algorithm for answering important questions
pery of a language class says that given languages
duces another language in the same class.
losure properties
be regular languages. Then the f
Union : LUM.
section | LAM
ywing languages are all regular.
Complement :
um
Reversal : LR = (a8: 0 € L}
Closure
Concatenation : LM jomomorphism
MY = fo eS: Ma)eL, h: E+ A* is a homom}
(220. Wite a short note on equivalence of regular
cag ulvalence of regular expressions en tte
14899 Is reguar it and ony -
prove te ng00 8 rear and nly some regu ex
2 12 laneUBQe is descrsed bya regular expression, then itis regular
; Tegulr, then there i a equa expression thet doseibes
a by & rp exreson, ton Hs rea” y
Some languzge A We will conver to an new wd
regular. Fihas one of sk possible forms
on describes i. Wo noag
2, Ra, for some a € 5.Then,
moO
3. R=2.Then,
ee cases, the constructions given in the proofs that the ciass of regular
re closed under the regular operations can be used here as well Ths is, we
‘assume Ry and Ra are recognized by NFA, N, and N, and use the samo constructions to
Create N from N, and No
@ 30. Find NFA equivalent to the following regular expression
(00+11)* 01
Ans. Let R, =0,
Re= 1.
Ry = AyF,= 00,
Ry=RRo= 11,
Rs= Rg+R, = (00+11)
Re= Ra" (00+1
Ry =RyRo=01
R= PgR,
regular Languages & Finite Automata a
‘Step 1 : The NFA for regular expression Ri is shown below :
Ry =0
= Oa O
co meh es oan
Oo-©
Step 3: The NFA for regular expression Ris shown below :
+O+O-+©
Fy =R,R; = 00
‘Step 4: The NFA for regular expression R, is shown below
Fy = RR= 11
‘Stop 5: The NFA for regular expression Rais shown below
Fy = Roy = (00+
Step 6: The NFA f
R= Re" 5s coma ne
(0+1)* (00411) (O+1)* 28 LOADS Theor of Compitaton
‘Now, we constuct the tansiion table forthe NOFA
State input
eo 7
ap Fo Tote
a % :
ay - w
@ au a
= ° i
cs) Toad
trou {a5
(Goal (Gol (Go.
Geasa> | toasat (0.440)
Goael [ease (Gos.
Transition table for the DFA
ts productions are type 3
productions. A production S-»A is alowed in type 3 grammar, but inthis case S does not
Eppear on the right-hand side of any productions, A production of the form A->a or A->8B,
where A,BEVN and ac5 is called a type 3 production.
23
Jed under the union
pegulr Languages & Fine Automata
@ 24, Prove that the class of regular language:
yular languages A; and A, be recognized by NFA Ny and Na , respective
‘construct an NFA N that recognizes AyUA2. N must
tate that will
1nd No= (Oz, E, Ba ag Fa)
recognize Ay Az using the following procedure
Is, the states of N aro
es on N; and Nz with the
2, The stan state of N is do
fof N are F = FyUF That i, the accept states of N are all the
nd Ne
shy qcQ and any acy.
itq= qo anda se ‘Construction of N to
Nis tke Ny, with a now start stato and an
and L, are regular languages then and {is also regular. Cy’ and : You can op (pire on ev op ao or oe i Se a A
ting sta
and prov pumping lemma or reper rons. pumping lemma we can write w =a in form of xyz that sates the
‘ (TU, Dec, 2020, 2019) tree condo ot pumpin lonrnn
| emma : Let L be a regular language, Then there exists a constant ‘Transition table for the DFA. ‘of a's and even number of b's.
Se a Te (PTU, Dee. 2011) ee Terror
fom state to state that occur "symbole chosen from an alphabet © Finite x
1 dra by a Sul (7, Fy wre oe = i afte ig
alphabet, q0 in @ is the inital state, Fis the set =—" map,
function Q* Eto Q.
Input tape, read contro! and finite control.
1. The input tape ie divided into numberof cell.
{rom the input tape changes state.
56, Briefly discuss the types of aut
‘Ans. Types of automaton : There are two types
2. Non-dete
‘A deterministic automata is one in which each
Is unequally determined by the
A tape to hod the put ting. The
= ela
sof three things :
of states thal the machine is allowed to be in (zer0 oF more
‘5 accept or final states
(PTU, May 2018)
diagram, a finite directed
is designated the start state and some of - ‘which the input stings are jg
2. An alphabot 5 of possible input symbols "OM NE ae of stata trom wn
8 Ante set of vncton dg bo) hat sh 2 ‘ine ot
Jon graph is eros of 65085 forming g
beginning at 0 and end ot oa state
‘Some of the transition graphs are given below =
Pat
rats
Transition diagram for a DFA
abet and the set of
slates, respectively, as
2. @y &Q, and qo is non empty; and
fansition table row of the table
the input a
‘Suppose we have a
‘corresponds to the state q and column correspont
States mpl:
a é
7 a %
% % 4
© cs %
Here the initia state in the table is represented with arrow on that state and the fi
~ state is represented by single circle.
‘ans. First
for every input signal
(NFA)
Transition table
State
Input
‘Start with intial stato
Stop here as there are =>
rho more reachable state
all construct a transtion table showing all reachable states for every state
lent to
by the following tabi
state | a b
> Catt 0
% %
% 9
e %
(PTU, Dec. 2018, 2017) _
og
Panacea Tretorn
" and where 5 is defined bythe folowing state table
State table
(99.41.4543)
“The vertex (qo) and (4,9) contains dp which is a final state of NFA. So, these are aso
final states of DFA.
@ 65. Consider the finite automaton and check the acceptability of following
strings :
(2) 0101, (b) 0111
polar Languages 8 Finite Akomata
‘ans. (a) The transition sequence for input string 0101 is as follows
Here, execution ends in fina
{) The transiton sequence for inp Toons
Here, execution ends in non-fnal stale qz, hence siting 0111 is not accepted.
@ 66. Construct DFA which accepts strings having odd number of a's and even
number of D's (PTU, May 2008)
Ans.
67. Design a deterministic finite automata over input alphabets (0,1) that starts
with 0 and end with 1 (PTU, May 2017 ; Dec 2011)
Ans. _—"_ > Se
pegulat Langu
rings over (a,0} ending In ab.
ar.
(9 71. Construct a DFA that accepts all strings that ends with 01.
Ans.
0.73. Construct a DFA that accepts
Ans.
‘Automata accepts strings ending in 1
0.74, Construct a DFA that accepts all strings having an odd number of 1s.
Ans.
° °
‘Automata accepts strings having an odd number of 1s.
Q75, Consrtuct a DFA that accepts all strings having an odd number of 1s and
odd no. of Os.
Ans. string with even number of 0 ‘corresponding to identifiers, constant, et0,
mation. 7:
designed based on finite automata. In general-
finite automata can recognize the
there is only one path
sition on each input
ofthe states containedin the sets &(it. 2), ing (b) Regular language.
deterministic machine moves to state. by a finite automaton M = (Q.5,6,qp.F) if 3(Qp.x) =p, forsome 0.101. For language L = {w € (a,b)*
Ans.
9 105. Consider the following
ition diagram and verify the following strings:
(PTU, May 2013)
102. For = (0,1),
Construct dfe's that accepts all strings with substri
ou Pl 198 with substring og,
2.010101 3.111100 4.101101
fans. 1. Accepted 2.
Q 107. Explain the acceptance of
Q 103. For 5 = (0,1), Construct dfa's that accepts all strings with ti
pcs 198 with third elemen,
Ans.
digraph (where vertices
‘One state is designated |
and a set of stales may be final stales, A NFA over an alphabet A is similar }
|
‘edges are allowed, there is no requirement to emit edges from state,
the same lett can be emits
alphabet, then 3* denotes the set of al strings over the alphabet including,
ing c, A language over an alphabet © is any subset of 5". We denole the size of
nd bya
@ 104. For 5 = (0,
binary number
Ans. ‘ulomata say | and m be equivalent if and or
3 state then &{rmw) must also be in final state and
MyhiltNerode theorem is used to eliminate useless states from a DFA, Esti) sae enaete eC? Ter corniay
"A Binary rition Fon oot Sf an opblonce ronion Ferd ont
1. Ris reflexive le. aa for all acS-
2. Riis symmetric Le, aRb = bRa forall a.deS:
3. R is transitive ie. ‘aR and bec = aA for alla.b.ceS- Bam
ann etmalnca elton Ron Sparano ies 2 eQUVAleRCe case,
Following are the steps to minimize a OFA.
Step 1. Detect the unreacnabe states
2. Eliminate unreachable states (it any)
3. identity equivalent slates ad merge tem
Q Group A - Accepting
Q Group B - Rejecting states of automata,
1D Repeat
O For every group
For every state in the group
1 Find which group the input lead toi there are differences then
into sets containing states which go to same groups under th
Unti no more parttion required
1 Resulting tinal patton contains equivalent slates now merge them into sings
state.
4. Detect dead states.
iminate dead states (i any)
id sets represented by regular expressions.
(PTU, Dec. 2015)
reguiar expression denoting the set
‘ab, ba, bb, 82a, ..-)
regular expression denoting the set
‘aa, aaaa, aaaaaa, ...)
is regular expression denoting the set
‘rust a Grammar which generates all even integer’s upto 998.
(PTU, May 2016)
B > 1i2is\567189 $9 AG, Ara,
an the procedure to convert NOFA to OFA
{An equal OFA
Greate state table trom the gven NOFA
‘Greate a blank state lable under possible
“Let us consider the NDFA shown in the figure below
é e4 aq
aa
ens
CContext-free grammars (CFG) and languages (CFL), Chom
‘nondeterministe pushdown automata (POA) and eavval
CFG, pumping lemma for context-free languages, det
properties of CFLs.
eg
Context Free Languages
& Pushdown Automata
Deca ona
Dern Soa
Selene
POINTS TO REMEMBER
Context free languages are used In defining programming languages, Sting processing
mbiguous grammar fit as rare than one le
ing of terminal symbol.
3s for specifying formal languages are
ative approach)
4, Grammar
2, Autbmaton (Recognition approac
‘Aunit production is a production AB where
[Unit production are redundant and hence should be
sentation forthe d
both A and B are non-terminale
removed.
jon of the given production
Derivation tree is a graphical r
rules for a given CFG.
‘Tho yield ofa derivation te the concatenation ofthe abels ofthe leavos from
rig
‘There are two types of normal forms. These are
4. Chomsky normal form
2, Grelbach normal form
“The language accepied by pushdown automala is contextree language.
“The input string is accepted by the PDA it
4, The final stato is reached.
2.The stack is empty.
“The language accepied by NPDA and DPDA are not equivalent,
GFL are closed under union, concatenation and Kleene closure,
64
nts Free Longue 8 Pusdoun Automata Py
GFL are closed under subs
FL are no
‘ne language L = {a°b” : n>=0)
‘The POA usually consiets of four componenis
aRaR
fee grammar.
Ge (PTU, May 2019)
2 grammar : A context free grammar (CFG) is denoted as G = (V;T,P,S)
sand terminals respectively. V and T are disjoint. P is
12 form A->a where A is a variable and a is a sting of
ns each is o
symbols from (VU
Q 3. What are the uses of context free grammars?
Descos beck seta prea nee
© Model neur ie ee
nots.
the language gen
ted by CFG or G?
juage generated by Gi
(ww is in T* and S = w)-That is a string is
19 Consists solely of terminals
ig can be derived from S. QS. What ie:
(2) CFL
(b) Sentential form.
‘Ans. Lis a context tree language (CF
AA string of terminals and variables « i
99.11S-> aSb| eAb, A> bAa, A be. Fin
. z . S-> abb = abab eae
= a, where S is the start symbol of the grammar. Ant 5 —> aSb = a aAb b=a aba b b(sub S-> aA)
6, What is the language generated by the grammar G = (V,T,P,S) where. §->aSb = aaSbb=aaahbbb=aaabal
P=(S-> aSb, > ab)? rus L= (a"0Parbn, where num>=t}
38
more than on
{(a) derivation (b) derivation/parse tree (c) s 'g 11. Find CFG with no useless symbols equivalent to
© Ans. (a) Let G =(V, the context free grammar. A> is a production of P and $ >ABICA, B>BC| AB, Aa, C aB Ib.
@ and y are any strings in (VUT)" then a Ay -»afiy. Ans. SAB im
SCA
(0) A tee i a parse/serivation tee for G B40
1, Every vertex has a isa symbolof VUTU {6} BAB
2, The label of the root is S. AeA
3. {fa vertex is Interior and has a label A, then A must bin V. een
4, ‘A and. vertices yfaynnnM Are the sons of the vertex n in order 6. b ave te que oneen
3p Xp) ony FOspoctvaly then A> x pep... Must be InP. °
(s father.
together with all its
fxn has label €, then nf leaf and isthe only son
(@)A subtee of a derivation tree Isa paroular vertex of thet
descendants, the edges connesing thom and thei labels, The abel ofthe root may not be ull productions are S->CA, A-ra, C-9b
the sant symtel of he grammar. (12, Construct CFG without c production from: S -» a|Ab| aa, A>
Ans. Sa
SAD
Saba
A> DA-9€ 8-90 B-> Aare te guen set of production.
‘Acs Cis the only empy production, Remove the empty production.
b|
@.8. Consider the grammar P = {$ -> aS | aSbS|¢) is ambiguous by constructing: :
(a) two parse trees
imost derivation
es S Ab, Put A-»€ and hence $36.
IS BA, and A¢ then B > €
A Hence $ — aBa becomes S > aa,
aod Thus S > ajAbjpiaBalaa
| Asb
@) 1. S>0s 2, $= aSvs Bob
= aaSbS eercosl Finally the productions are: S—>a|Ab |b|aBal aa
= aabS = aabS Asb
= aab = ab Bob te frm A> B where A and B a0 variables,
tor the language L= {embewwhere r>1)
) here P
The minimum sting is $-> 0
$— 0S1= 001
S012 011
> Si 00511 = o00St11—= 0000
Thus Le{0"" | minot eau es
147. Consinict the grammar forthe language L = (2"®
‘Ans. Tho grammar has the producon P as
Rissa ;
100000111
PS)
guage L which has
<8.) which i in palindrome.
@ 18, Differentiate sentences vs sententil forms. 3
‘Ans. A sentence isa sting of terminal symbols, A sentetial form isa sting cons
4 mixof variables and terminal symbols o all arabs. Ths isan intermediate form ind
A detvai
‘0.20. What is a formal ianguage 2
_ Ans. Language is a set of valid strings trom some alphabet. The set may be ert
finite or infinite, L(M) isthe language defined by machine M and L(G) is the language det
by conten fee grammar. The tvo noltons for specitying formal languages are
4. Grammar of reguar expression (Generatve approach)
2, Automaton (Recogation approch)
saa aba
SaCa-aaCaa=aabaa
$>aCa=aaCaa=aaaCaaa aasbaaa
“Thus L(G) = (@" b atwhere
)
G23. Find L(G) where G = ((S}, (0,1},{S + 0S1, S + €), 8)
fans, Although natural and
Janguages are not formal
reduction is a production A -> B where both A and B are
sdundant and hence should be removed. Follow the
produetion. :
exist a production B-ra, where ais @
terminal
For every non-unit production, Bra repeat the following step
‘Add production A. to the grammar,
3, Eliminate AB from the grammar.
For Example : Remove the unit productions from the following grammar :
SAB
Ava
B> cb
C5D
Doe
Esa |
prime} is not a context free language. 1
aaa (PTU, Dec. 2005
el such thal iw.
oe
(PTU, Dec. 2020, 2013
[prammat is ambiguous we need to find a string weL(G), Li le
‘As there are more than one tree being generated fr the given sting, the given gram,
|S said to be ambiguous grammar.
@.27. Show that the grammar S->aB/ab, A aA Bla, B ->ABbID Is ambiguous,
(PTU, May 2097,
‘Ans. Consider the word ab, The iio leftmost derivation of G are
Sab
S=AB= ab
‘Thus ab is ambiguously derivable by the grammar and so the grammar is ambiguous,
Q 38. Define Chomsky normal (PTU, May 2017 ; Dec. 2008)
‘Ans. Chomsky normal form : A context-\ree grammar G i in chomsky normal form
CONF if all productions are ofthe form
ABC
or Ava”
Where AB and C are variables
39, What are the steps need
‘grammar In chomsky normal form.
Tans, Step 1 Elimination of nul productions and u
tliinate nul production by applying the theorem that if G = (VS.
‘grammer, then we can find a contexte grammar G' having ro nul productions
a terminal
reduce @ context free grams
ns by applying the theorem that If G be a context
free grammar G!
HS, say alis te
production ©,» al oP"
Every terminal i
|. All productions in P"
in V'n are added to
2, there are prod
new productions.
jons of the
Free Languages & Pushdown Automata
Cn-2~ Ayn and new ve
jyctions
ee p-2) are added to VN. Th
x
'q 40. Convert Context free grammar Into Chomsky normal form
'S > XaX | bX
X > Kax |Xbxie
(PTU, Dec. 2011)
First ofall we X is nullable variable
remove production XE.
“Then, we have
'S > Xax|bX\ \b
X-> Xax! XBX/Xal ax} Xo/bx/al b
stop 2. Elimination of unit productions: There is no unit production exists in this
grammar p
Step 3. Convert terminal into non-terminals
‘Ada productions 2,-» @ and 2,-» b and replace productions,
$+ xax with Sx2,X
Sox $>ZX
S$ Xa 8X2;
Sax S32X
X > xax X9XZ.K
X XOX X XZX
Xo Xa X>Xxz,
Xo aX X49 ZK
Xo xb Xo XZ,
xX bx XoZX
Step 4. Now add productions
¥;=2Z,X and Yz= ZX, and replace productions
$+ XZ,X XY,
X > XZ3X XY;
X > XZX Pa :
Now the g is in Chomsky normal form and consists of following productions.
112_x
al XZ ZX! XZql Zxlalb
Q 41. Explain the concept of Greibach normal form in detail.
(PTU, May 2019 ; Dec. 2018)
ee grammar G=(V,
isa string of
A product
Fecursion in R can be wwe have to remove left recurs
ike A t - 4 Ago DAgAy [DIDARAAZIOZ
nie i 4 2 AAA 3
e then fi ; 7
Beeciae= coe
hy > Ae AAA s
set of product
Bete
Ak > Aly aproducton wih jek, generate a=
for the A\ the body of each A; production.
Repeating (o) at most K-1 times we obiain res ofthe forn A,
{@) Replace res A, -> Ay by removing lefecursion as stated above
f-2, in desied or at he same time change hy
we
Z production rls.
"142, Conver the following grammar G into Grelbach normal efor Ac and Ay to convert to GNF Ay-> bs | BASRA
4 $ > XA|BB for Z> AADAC :
Bone subst for A, to comet ito GNF Z Ay AI
Xob DAdZ|DASALZ AZIBZA,Z na ac
E Asa 4. Fay the grammar ih GNF
‘Ans, To wie the above gram ‘Ay DA DAah Ay] DAI BAYA,ZAYIBZAy
al producto
cy a Sa ‘donot conform to any of the types listed below
|i Ain such that jen
Ai vary such that xev" and acT
Ay > AAD
As the given grammar has no rul productions and are in CNF, so
ii osm» FomalLanguge & ay
: guired form etanguogestPushdowm tomate
Step 2 : A, production are in the opie :
1A Mahal oe
2. Ag bis in required for. = AyAy begins With atone, :
“Since the sight hand side ofthe prducion fz
fn
irenoa of Ay both ApA2 and a. Thus the py, M
variable, we substitute for tho frst oo "oy .
laced by (q 44. Reduce the following Gram
Ago aA one, A > BSB, A> BB, B > aAb, Bra, Ab
‘Thus Ay productions are Jas. Step 1 : Replace B->aSb by B ~ aSC and C-rb. Rename SAB and C by Ay, Ax
> AA, ib
rn aa tay ho ht
a =. ty necessary for G,. The only A, production Ay->b is
theorem 2 {0 Az production (as j=!) ‘Ap productions are
Step 3: Now, wo have to aly AAA AalabAyID
Asha Aa
Aon Ape Ay| aD
Ao |@Ag Ag AAA IAs
(AglaAs lana, AAs!
>b,
to finite subsets of Qx T°.
THEA
.ge accepted by NFA'is the | 7. Thelanguage accepted by PDA\s contexts
reelanguage.
DA is essentially an NFA with a stack
(memory)
stores unbounded limit of information.
ited amount of |
Hence the equiv
9 's accepted only by | 4. accepts language eltherby emply stack
+= (Aye re : |__orby reaching afinat state LosDD Formal L2n0U296 & Aipy
ct moves in PDA.
‘he input symbol
ten
I, zis slack symbol and
stale,
Q 47, Specity the two types
Ans. The move dependent
(a.
‘here q and pare staies, 28 in
‘with input symbol a and Z the top symbol o7 See
Replace symbol Z by string ¥)
‘The move independent on input symbol is ( oe ay
Pd SCaNnEd arity
5
inguage acceptances by a PDA any
ne
ther ty
rnguage accepted by i
3) for some pin F and
true the language acepe by 2 PDA By emPtY SK a tal yy
ngusges.
‘Ans, No, because the language accepted by PDA's by fi
Janguages accepted by PDA's by empty sick
© 50. Define deterministic PDA
Ans. A PDAM = (O.578dp29F) is deter
‘© Foreach qin @ and Zin, whenever 8,
forall ain
© Fornoqin Q, Zin 1, and @in Yu (e) does 6(a.2.2) contains more tan og
element (Eg): The PDA accepting (wen | in (+)")
151, Define instantaneous deserintion (iD) in PDA
Ans. ID describe the configuration ofa POA at a given in t
is 8 tbe sich
(Givi), where qi. state, wis a sing of input symbols and ys a string of stack syméne
M=(Q.5,,8,q,Z9) is a PDA we say that (q.aw Zu) | ~~
‘ay be €or an input symbol. Example: (4,26) sina, 0,
1,BGGR). c
Q 52. What is the significance of POA?
Ans. Fine automata is used to model ro
model regular expression and cannot be usé
represent non-regular languages, Thus to
apres ges. Thus to model a context free language, a pushdot
Q 53. When isa string accepted by a PDA?
‘Ans. The s
eth
State are exact
is nonempty then (918.2) ie en
eo tanguages & Pus Automata
i
eT give examples of languages handled by PDA.
‘L= (a%B"| n>=0), here nis unbounded, hence counting cannot be done by
we requite a PDA, a machine that can count without iit
{ww € (0.0) fo handle this language we need unlimited counting capability.
Is NPDA (nondeterministic PDA) ant DPDA (deterministic PDA) equivalent?
re languages accepted by NDPA and DPDA are not equivalent. For example =
ied by NOPA and not by any DPDA. : i
equivalence of acceptance by final state and empty stack.
some PDA Me, thon k= N(Ms) for some PDA My.
some POA My, then l= L(M) for some PDA Ma.
by PDA by reaching a final state.
by POA by empty stack.
.quivalence of PDA and CFL.
is a context free language, then there exists a PDA M such that L = N(M).
for some PDA m, thon Lis @ context fee language.
0.58. What are the closure properties of CFL?
1 properties of CFL
concatenation and Kieene closure
Ans, The
wis 208
lersection, complementation.
‘are used to prave that certain languages are not context free.
the pumping lemma for CFLs. (PTU, Dec 2008)
‘Ans. Pumping lemma for CFLs : Ket L be any GFL. Then there is a constant n,
depending only on L, such that iis in L and j= n, then 2 = uwoy such that
4. vaie=t
=n and
ib=0 uvinndy isin L.
(2.60. What is the main application of pumping lemma in CFLs?
smma can be used to prove a variely of languaget
3 are not context
Q 61. What Is Ogden's lemma?
Ans, Let L be a GFL, Then there is a constant n such that
‘atk any n or more positions of z distinguished" then we can wit
1. v and x together have atleast one distinguished positon.
2. vwx has at most n distinguished positions and.
3. forall >=0 uviwx’y is in
ic CFL.
del
62, Give an exampie of Determi
‘Ans, The language L = {a"b"in>= ie CFL PDA. "
ors cctermatsel
Ratslrcsi one
any {D. *
irnas a read-only input tape, an input alphabet, a finite s a
case ofan FA. In addition to these, ithas a st
El
ly consists of four components,
Bee. a new ale. The pusicowr nora ales see
Ji clan th topmost symbol n PDS, moves toa new stat and wri 8 stig
nition of PDA?
al machine fo recognize context reo lang
yeen init automaton and turing machines. The POaie
as a stack,
i Bec fe nonempty set of pushdown symbols called stack alphabet. It isthe set of
Ve (ab}*)is a non-determinisic CFL.
(PTU, Dee my
‘to the set of finite subsets of Q x.T~
XT, we do not mention i.
strings over {2,b) with equal
(PTU, Dec 2008)
ot where 8 is defined by the following rules
AA such that A = xy if
derives the first symbol
wand c derives the be
down automata,
(PTY, Dec. 2018, 2018, 2010; May 2017, 2 » g
computational machine to recognize a cortettM# 173. Design a push-down automata for accepting @ language L = {atbn| nz0)
‘is between finite automaton and turing machi (PTU, Dec. 201
land the memory is organized as a sia¢k Ans, This is a language in which equal number of a's are followed by equal ni
ie
ik a {@ 76. Give an example which shows that
ful than deterministic push-down automata.
‘of NDFA, OPDA and FA)
(PTU, May 2019)
‘automaton (NPDA) is a ~
{unction.
(PTU, May 2019)
APDAP = (OS. 8qZoF)
aT, 8qaX)= 2. An
move is possible,
allowed transition trom any 1D. Ihe NPDA pops the top symbol of the g
i fementy reading, ard (2) curen ag
that appears atleast twice in the path of the
the vertices labeled withthe ‘context free languages,
Pr ‘ ntext-free (in fact regu
languages : Context-oe roatoset arb" and aPb"e” consis the cote re aust (a
Janguages ar closed under unjon,
isat symbols S and T. Rename
languages, with start symbol Z, by
new tule Z > ST.
he language L, with star symbots
alle res tom the origina grammar put
4, String reversal : Reverse the character string on the righthand side
‘product construction to create a PDA which simuistos
‘because only M needs to manipulate the stack ; N nei
Sot complement Ralieoe il
deMorgan's laws to show that closure alle peer: language, then we can
2. L= NA).
(PTV, May 2019 ; Dec, 2015)
‘Ans. We construct A by making use of productions in G. ating w. The stove of Aig
Sand tes UsAyay Then
§ Aap = Uayo9 = uo.
e second case, it can be spl
then
we prove itby induction on the numberof segs
@=A,and S=A.As (a, v, 8) (
= a, So.we have (qu) * (a
Aa. By the prince of induction, it is true for any derivation. Now
We L(G). Then, w can be obtained from a leftmost derivation Hore vie use symbol 4 to indicate both the end of input, and the result of popping from
‘an empty stack. arthan S-»2) involve on the right side 25 ang
(ce any pn ol the devivallon Is ProvGe ig
dings. We have to finally apply S-»?. certain rumbe,
In second rule C,AA is not in CNF. So we can replace AA DY#
ee
'S 00810101,
S > 0011010
‘Ans. Taking a string abababb, The string can be generated in the fo
(a) S > abSb + abaAbb — ababSbb — ebababb
5+ Ab > abSb > aba bb > ababSbb > abababb
Parse trees for (a) and (b) wil be :
Q
Cao
SHO
6 &
re geting vo pats wee for aperaing sting Ko he gen gamma, 30 he
ree :
Compa the com ng a pushdown symbol given by (@y, 2y, Za =u)
Production ofthe form ss
(4a Za al a
Ge» Gn can bo any stat in Q.
K 2) yielis
P30, Za, Gol > M1» Ks Ql foe Zor Ga . there are more than one
fins oxamine the productions posal
1g = 1A08 => 110108 >
diffe
ich is accepted by the PDA but not by
2 (TU, May 2018)
pin the context ro grammar G es 1)
sigle mar
imbol. Non-accepting string examples are these.
instate S
ab in state S with non-empty stack
sn consumed input and emply stack.
Observe that this PDA is deterministic in the sense that there are no choices in
istons.
‘The second example is
middle is coming,
Q.98. What are normal forms of CFG ?
‘Ans. A CFG is in Chomsky Normal forms if the productions are in the following forms. 2, Cellular automata model spread of eisease
ing messages by cellular automata, which produce very sto
compression gives very good results, if
‘GNF equivalent to the grammer
ESET > TEEE > (eva,
ans, E> E+ TIT
ToT Fr
Fo (ey
form A > c where. A's avaible ay
called the start symt
rE > E + Elid We can croate te pane
sath = States 7 ve. shifVreduce conflets for + and ~
bi EE I EEE Context Sensitive Languages
Context-sensitive grammars (CSG) and languages, linear bounded automata and equivalence with
cs.
POINTS TO REMEMBER fe 4
= Context sensitive language is a language that can be defined by context sensitive
grammer,
@ Linear Bounded Automata-defined a restricted form of turing machine.
QUESTION-ANSWERS
Q 1. What is context sensitive language ?
Ans. A context sensitive grammer whose productions are of the form
aAB > arf
Where «, B € (NUT) *, A EN, Ve (NUT) + and a rule of the form S->4 is allowed if the
slart symbol S do not appear on the right handside of any rule
The language generated by such a grammer is called a context sensitive language.
© Every context - free grammer is also context — sensitive = > the context — free
languages are a subset of the context — sensitive languages
O But, not every context — sensitive language is context free.
Q 2. Consider the following CSG :
S > abc/aAbe
Ab bA
AC > BbcC
bB > Bb
aB — aa/aaA
What is the language generated by this grammer ?
Ans. S > aAbc
— abAc
— abBbec
> aBbbec
+ ~ aaAbbec
101 ncn TT me
Hoe per cnn popes, ares
Nondeterministic TMs and equivalence with deterministic TMS, unt
‘equivalence with Turing machines, TMs as enumerators.
POINTS TO REMEMBER
i ® Turing machine is a simple mathematical model of a computer.
ca xd and unresicled memory and is @ much more aca
eee
5] The ID of a TM M is denoted as 9 a2.
Sai epson tng matin tsa na
= 192%] and 220 ary
| & oa
La include languages accepted by atleast one Tr ‘on all inputs,
"3 We can describe turing machine using
(@) Instantaneous description
Transition table
(c) Transition diagram
© TM recognizes recursively enumerable languages.
© Variants of TM are
4, Non-deterministic TM
pe TM
3, Enume:
pondence problemis an undecidable decision problem that was introdutt
1946.
has external memory which is capitl
arbitrary long sequence of input
Turing machine is powerful more than fnite automata,
104
91. What is Turing machin
fans. Turing machine : Tung machine fa simple mathematical médel ofa comput
nq machine has unlimited and unrestricted memory and is a much more accurate mode)
general purpose computer. The tung machine i a FA with a RAW head, Ithas an infinite
lA cells, each cell holding one symbol.
'M depending upon the
2, Prints a symbol on the tape cell scanned, replacing what was writen there.
3, Moves the RIW head left or right one cell
Q3. Define Turing machine,
(tp. Here q is the current state of Mis in Q;
i tape up tothe rightmost nonbank symbol or
ad, which ever is the rightmost.
tions of TM? s
19 machine ; Turing machine can be used as
guages,
ns on non negative integers.
difference between 2-way FA and TM ?
ine can chainge symbols on its tape, ahereas the FA cannot change
fymbols an tape. Also TM has @ tape head that moves both left and right side, whereas the:
FAdoesn't have such a tape head.
Total recursive function and (b) partial recursive function,
ik then we say fs a total recursive function.
Qxft0OxTx {LA}
stantaneous description of TM, (PTU, Dec. 2019) . 4030 Formal LNGUIGE 8 Auton
Tongue said Be recursig
G28 when dreoir ie nrtriiele turing machine Is dite. q 32. Define universal turing machine,
that the language accepted ’
ges. Universal turing machine: A universal ting machine (UTM)
recursively enumerable aN? spree 68 TM M2000 Landa | any eer turing machin ftom the description of the machi
Ans. language Lis 2488 MTT guage Is Nd B°epIab ang Hm CPS 55 Ge the formal definton of turing machine. “
" a Tal szanes P fans. Formal def
language is turing deca ceteris wing machine Is same nana
‘ron determi 2M goto
No, he language accepted by nor Mongy (5 5 rer pl cot aes ye
rionempy set of tape symbols, 2
ett tg conn oman tie ee
T churehTuring thesis. The turin put symbols and isa subset off an
oe 9 nein 5 ston function mapping (qx) onto (q.y,D) where D denotes the direction
to determine the given number is pg
.
Q 26. Explain how a TM can be u
F< Ois tho sot of inal states or accept
@.84, Design a turing machine M that recognize the language (172"3"
inary on the Second track anc (PTY, Dect 21 Nien
oe Se any ince se " a {et us evolvé a procedure for processing the inpul string 112233,
the tid track by the second 12283 b1q,2299 + bibqy299 + bIb2q9 F bIbabqa E
2263 + bgctb2b3. | qgbtb2b9. + bq,Tb2b3Hbbq,b2b3
greater than 2, writen on the
‘nthe second trac.
ion?
‘computes, changes occur in the curren
lale. The RIW head scans the leftmost 1, replace 1 by b, and
5 Go
(On scanning the leftmost 2, the RW head replaces 2 by b and moves to the right, M
centers 43
the cure
configu;
ihe FIW head replaces 3 by b, and moves
3, the RIW heads moves to the left until
‘and 3 ate replaced by b. Steps 1-4 are repeated until
laced by blanks.
‘Transition Table
‘nondeterministic TM? Tape symbol
ly chooses move when more than ly exists Present state 4 3 Bisel
S ets alleast one computation in an acceping i BR BAG;
Algorithm? & TRay Da: BAG
's a collection of simple instruction for carrying out some tse 93 CREE bRas RG
sometimes called procedures or recipes. Beag carrying out ‘Gs Las La;
Q 31. Whi ting problem? as La. Blas Las
‘Ans. ATM M is @ TM and M accepts w. Th lh 6 Tha s DRG: :
= M Ais undecidable but TM A
scopunietetce TU A bam oer he tc © | Load Formal Language &AUtoM ata Thea)
sings ae han those af th form
‘M enters ay.
‘scanning the leftmost b, the FIW head replaces b by X and moves to the
‘Step 5 : Step 1-4 are repeated until all as, bs and c's are replaced by blanks.
The change of ID due to processing of aabbcc is given as
oaabboo }-Xayabbec }Xagybbec -XaXazbor |. Xaxbqaco | XaXbXdge -XeXbaske
IpXaxa,exe -Xaxa,XbXe pXqaXbXe +agxaXbXe -XapaXBXe |-XXq}XOXe |-XXKg\DKe
ROOK GEKe - OHOKK G6 - HHHHK GX | XXXKGHK
‘Transition
tape symbol
RG;
aay
(0.36. What do you understand by acceptably of |
fans. A ting machine M = (O3,7,5.996 qf) accepts ta
tae beorgs 0) the ung machine Mw esos het
pring machine does not accept L i ator reading w its notin stale a oF
7s sTe[e}
Input and output tapes
(ur main task is to remove the symbol b. Now, this ean be done in.the following
Current Tape symbol
Present state 7 3
90 TRap TRG,
a Ray bla
a bLqs a
a3 Las * brat
© : -
158, Design a turing machine to recognize all strings consist
numberof 1
Ans,
CurrentiPresent state
Ge ea
S111 + bagi Fbbq,. AS qy ig an accepting stato, 11 ie accepted
—— =. 2 Lor» Formal Language & Automata Theory esti a
Here, qs the inal or start stale, M enters the state q2 on scanning 1 and writes by (neon the runber of RW head
Mis in state gp and scan 1, it enters q, and write b. ay is the only accepting state, -” ee ee ¥
@.39. Design a turing machine M to recognize the language ioral a (Casco mouicalone viata eee
restos tre mectre or gen ungueg sshor noting tre:
fefinition and moves,
tts fo ome
‘Ans. Alan Turing proposed the turing machine as a model of ‘an
ing mecrne 2 TO pOwertl han PDA Thi ean el
Accepting computation : qzaabb }-Xq,abb + Xaq,bb +-Xq,aYb Ha,XaYb aya
HKG YE HXXVG;D EXXGLYY EXGRXYY HXKGQYY EXXY GY HXXYYggB FXXYYBQB
ring machine and modification of basic model of
(PTU, Dec. 2009)
sal turing machine : A general purpos
‘Turing machine (UTM) when itis poweriul enough
2. Deseription of computation (algorithm or prog
vrpose computer does. It accepts data and progam. Turing Machine Model
ALany tne, action ofa tring machine
eee 36 machine depends on he cuenta and th
ee cane! ‘symbol and involves. a
4, Tuting machine
‘turing machine may
cells beyond the input imits and ‘Blank’ cel
Modification of basic model
that even with very signed 1
‘even a simple behavior. states.
symbols, not including 8.
‘non-empty set of tape symbols or tape alphabets.
is called initial or start state.
Fis the set of final or accepting state.
be.
‘bis the transition function defined as, ves the
overnent of the |
dx OxT= LA) fe pene St wh eg rach
example :
Current! ToS
_ present stale o 7 ;
2a OF;
A ORs
‘Suppose alter reading symbol
symbol b onthe tape and the head mo jagram the labels are tiples of the form
of following move. rected edge from ato «with label (4.
Blae-ag) = (25.7)
8s) = (Go, and RAW head scans the present symbol a. AS a result, the symbol Bis
‘The move can be writen with the help
an + 2,229;
denote the reflexive
FIW head. The RAW head moves to the left or ight, depending on 7
sive closure of the relation.
@ 42, Explain the various representation of a turing machine.
> (PTU, May 2019 ; Dec. 2020, 2017)
‘Ans. We can describe a turing machine using -
4. Instantaneous description (ID)
2. Transition table
4. Transition diagram
+ instantaneous description using move relations : Instantaneous des
in PDA was in terms of current siate, input string to be processed, and
PDS. But in turing machine the R/W head can move to the left also. So 1D.
is defined in terms of the entire input string and curent state. During @
