Introduction to Languages and the Theory of Computation
Class notes for Theory of Computer Science, Computer Engineering (SEM V), covering important sums, solutions to questions from past papers, easy and complete methods to score full.
FSM page1
Ends With
100 page2
Bba page4
Abb, 1011, 101 or 110 page5
011 page7
Second last symbol is “a” page6
Contains
Aba, 110 page6
Does not contain 010 page7
N
Does not contain 3 consecutive a’s, contains atleast 2 a’s page8
O
contains atleast 3 a’s page9
3 a’s page9
TE
Contains atmost 3 a’s, odd no of a’s page10
Even no of a’s, even a’s and odd b’s, odd a’s and even b’s page11
S
Divisibility
Binary no divisible by 3, by 4 page12
B
Ternary no by 5 page13
Regular Expression page14
Y
RE to NFA page17
a(a+b)*b page19
A
(ab + ba)* page20
K
Strings ending in “aa” page20
(0+1)*(10)*(0+1) page21
(0+E) (10)*(1+E) page21
Strings that end either in 01 or 101 page22
DFA page22
Strings ending in “aa” page24
R = (11 + 10)* page25
R = 0*1*2* page26
R = (10 + 01)* page27
Convert NFA with epsilon to DFA page28
NFA with epsilon to without page30
NFA without epsilon to DFA page31
Finite Automata to RE page33
,Direct DFA construction
Strings ending in 100 page38
Strings ending in 1011, contains 110 page39
Does not contain 010, contains atleast 2a’s page40
Atmost 3a’s page41
Binary no divisible by 3, by 5 page42
Beginning with 1 and decimal value multiple of 5 page43
Language containing all strings over {a,b,c} that starts and
page43
ends with different symbols
Differentiate DFA and NFA page44
Moore and Mealy page44
Moore Machine
Output ‘A’ if input ending in 101, ‘B’ if 110 and ‘C’ otherwise page45
N
Output the remainder when binary no is divided by 3 page47
O
Output the remainder when ternary no is divided by 5
Change each occurrence of 110 to 111 page48
TE
Change each occurrence of abb to aba
Mealy Machine
S
Output ‘A’ if ending in bba and ‘R’ otherwise page49
Output even/odd no of a’s
B
Output the remainder when binary no is divided by 3 page50
Change each occurrence of 110 to 111
Y
Change each occurrence of abb to aba
page51
Binary adder
A
Differentiate Moore and Mealy page52
K
Moore to mealy and vice-versa page53
Design Moore and Mealy machine to find 1’s complement of
binary number page55
2’s complement
Mealy/Moore machine for r = (0+1)*(00+11)
page56
(ab aur 10 ka dhyaan rakhna)
Grammars
Chomsky’s Hierarchy page57
CFG (derivation) page58
S -> aAS | a
A -> SbA | SS | ba
page59
Derive “aabbaa” using LMD & RMD. Draw parse tree.
,S -> aB | bA
A –> a | aS | bAA
B -> b | bS | aBB
Derive aabb, baab, aab
S -> SAS | b
A -> ba | b page60
String “bbabbbbab”
Ambiguous grammar page62
S -> iCtS | iCtSeS | a
C -> b page62
String “ibtibtaea”
Writing Grammar/CFG/CFL
Start with a over {a,b}
N
End in 10 page64
O
End either in 00 or 11
Start with a and end with b
TE
Contain aa page65
Contain atleast/exactly/atmost 2 a’s
L = {an bn | n >= 1}
S
L = {an b2n | n >= 1}
page66
B
L = {a2n bn | n >= 0}
L = {am bm-3 | m >= 3}
Y
Simplification of CFG page67
S –> aS | B
A
page69
B -> b | c
K
S -> aSb | A
page70
A -> c | epsilon
Chmosky normal form (CNF)
S -> aA | a page71
A -> aSa | b
S -> XYX
X -> aX | a
Y -> bY | b
page72
S -> ASA | a
A -> bA | c | b
S -> aB | bA
A -> a | aS | bAA page73
B -> b | bS | aBB
,S -> Sa | A
page74
A -> a | b
S -> aSb | bSa | epsilon page75
S -> ABA
A -> aA | bA | epsilon page76
B -> bB | aA | epsilon
Greibach Normal Form (GNF)
page77
S -> ASA | AA
A -> bA | c | b
S -> AB | BA | ABA
A -> aA | b
B -> bB | a
N
page78
O
S -> AB
A -> BSB | BB | b
TE
B -> a
S -> ad | aA
A -> aSa | b
S
page79
B
S -> ASB | a | bb
A -> aSA | a
Y
B -> SbS | bb
S -> AS | a
A
A -> SA | b
K
page80
X -> YY | a
Y -> XX | b
S -> SS | aSb | ab page81
S -> XA | BB
B -> b | SB
X -> b
A -> a page82
S -> aSb | aX
X -> Xa | Sa | a
Push Down Automata (PDA)
page83
Model
Design PDA to recognize L = {an bn | n >= 1} page84
,L = {0n 1n | n >= 1} page86
L = {an b2n | n >= 1} page87
L = {cn d3n | n >= 1} page88
L = {an bm cm dn| n >= 1}
L = {an bm an | m, n >= 1}
page89
L = { WCWr | w – any combination of a’s and b’s
wr is reverse of w}
Language containing equal number of a’s and b’s page90
Language containing num of a’s are greater than num of b’s page91
Check well formedness of parentheses page92
CFG to PDA
N
page93
O
S -> aSb | bb
PDA to accept the language L = {a2n bn | n > 0} page94
TE
L = {an+1 b2n+1 | n >= 1} page95
Turing Machine
page96
S
Model
L = {an bn | n >= 1} page97
B
L = {an bn cn| n >= 1} page98
L = {an b2n | n >= 1} page99
Y
L = {a2n bn | n >= 1} page100
Equal no of a’s and b’s
A
page101
No of a’s greater than no of b’s
K
Check for palindrome page102
Perform m monus n page103
Perform m+n page104
Check well formedness of parentheses
page105
Types of TM
Perform m*n
i/p: B0m | 0n B
page106
o/p: B0pB
p = m*n
Applications of TCS page107
Pumping Lemma by proof of Contradiction
page109
L = { aibi | i >= 1}
L = { aib2i | i > 0} page110
,L = { 0i^2 | I >= 1} page111
PDA for L = { aibi ci| i >= 1} page112
L = { ai| I is prime} is not CFL page113
N
O
TE
S
B
Y
A
K
, K
A
Y
B
S
TE
O
N
, N
O
TE
S
B
Y
A
K
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper notesbyak. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €3,41. Je zit daarna nergens aan vast.
