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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller notesbyak. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.49. You're not tied to anything after your purchase.
