II B.Tech(CSE) II Semester
Academic Dairy
for
Formal Languages and Automata Theory
Faculty Names: Mr. P. Anjaiah
Mrs. S. Kalyani
Mr. C. Pavan Kumar
Formal Languages and Automata Theory
( II B.TECH(CSE) II SEM )
Micro Level Teaching Plan
Unit No / Topic / hours / Lecture DateI / Fundamentals : Strings, Alphabet, Language, Operations, Finite state machine / 2
Definitions, finite automaton model / 1
Acceptance of strings, and languages / 1
Acceptance of strings, and languages / 1
Deterministic finite automation / 1
Deterministic finite automation / 1
Non deterministic finite automation / 1
Non deterministic finite automation / 1
Transition diagrams Language recognizers. / 1
10
II / Finite Automata : NFA with ε- transitions
NFA with ε- transitions
NFA with ε- transitions
Significance, acceptance of languages
Conversions and Equivalence : Equivalence between NFA with and without Î transitions
NFA to DFA conversion
Minimization of FSM,
Minimization of FSM,
Equivalence between two FSM’s
Finite Automata with output
Moore and Melay machines.
Moore and Melay machines. / 1
1
1
1
1
1
1
1
1
1
1
11
III / Regular Languages :
Regular sets, regular expressions, identity rules, /
1
Constructing finite Automata for a given regular expressions / 1
Conversion of Finite Automata to Regular expressions / 1
Pumping lemma of regular sets / 1
Closure properties of regular sets / 1
6
IV / Grammar Formalism :
Regular grammars-right linear and left linear grammars / 2
Equivalence between regular linear grammar and FA / 1
Inter conversion Context free grammar, derivation trees / 1
Sentential forms Right most and leftmost derivation of strings. / 1
6
V / Context Free Grammars :
Ambiguity in context free grammars /
1
Minimization of Context Free Grammars. / 1
Chomsky normal form, Greiback normal form / 1
Pumping Lemma for Context Free Languages / 1
Pumping Lemma for Context Free Languages / 1
Enumeration of properties of CFL / 1
Enumeration of properties of CFL / 1
8
VI / Push Down Automata :
Push down automata, definition, model, acceptance of CFL, /
1
Push down automata, definition, model, acceptance of CFL, / 1
Acceptance by final state and acceptance by empty state and its equivalence / 1
Acceptance by final state and acceptance by empty state and its equivalence / 1
Equivalence of CFL and PDA, interconversion / 1
Introduction to DCFL and DPDA / 1
Introduction to DCFL and DPDA / 1
8
VII / Turing Machine :
Turing Machine, definition, model, design of TM
Computable functions, recursively enumerable languages.
Computable functions, recursively enumerable languages.
Types of Turing machines / 2
1
1
1
6
VIII / Computability Theory :
Chomsky hierarchy of languages / 1
Linear bounded automata and context sensitive language / 1
LR(0) grammar, decidability of, problems / 1
Universal Turing Machine / 1
Undecidability of posts / 1
Correspondence problem / 1
Turing reducibility, Definition of P and NP problems, / 1
NP complete and NP hard problems. / 1
Total no of hours / 8
64
Formal Languages and Automata Theory
UNIT I
Fundamentals : Strings, Alphabet, Language, Operations, Finite state machine, definitions, finite automaton model, acceptance of strings, and languages, deterministic finite automaton and non deterministic finite automaton, transition diagrams and Language recognizers.
Objectives:
· To know the fundamentals of automata
· To learn about the DFA & NFA.
· To learn about the transition diagrams.
Topic / Lecture Date / HoursFundamentals : Strings, Alphabet, Language, Operations, Finite state machine / 2
Definitions, finite automaton model / 1
Acceptance of strings, and languages / 1
Acceptance of strings, and languages / 1
Deterministic finite automation / 1
Deterministic finite automation / 1
Non deterministic finite automation / 1
Non deterministic finite automation / 1
Transition diagrams Language recognizers. / 1
10
Applications:
1). The finite automata concept is useful in design and development of any kind of
application.
2). This concept is useful in design and construction of compilers.
Important Questions:
1. Define DFA and NFA. Explain the difference between them with example.
(May/june 2009 set1)
2. Construct a smallest DFA over Σ = {a,b} accepting all strings which have number
a’s divisible by 6 and number of b’s divisible by 8.( . (May/june 2009 set 1)
3. Define a finite state machine and explain model of finite automaton.? (. (May/june
2009 set2)
4. Provide an NFA with at most six states for the following language:
L={w | w contains an even number of 0’s , or exactly two 1’s}.. (May/june
2009 set2)
5. What is the Block diagram of F.A? Explain the characteristics of F.A?. . (May/june
2009 set3)
6. Provide DFA recognizing L={w a {0,1}* | w contains at least two 0’s and at most
one 1}. (May/june 2009 set3)
7. Find the language accepted by following finite automaton: . (May/june 2009 set4)
8. Construct DFA and NFA for L={w å {0,1}* | w contains the substring 0101}.
(May/june 2009 set4)
9. Design a DFA for the following language. L = {0m1n/m _ 0 and n _ 1} . . (Nov
2008 set1)
10. Represent all five tuples for below transition and decide whether it is DFA or
NFA. (Nov 2008 set1)
11 Design a DFA that accepts the language L(M) = {W/W< {a,b)*} and does not
contains 3 consicutive b’s.( (Nov 2008 set2)
12. Draw the transition diagram for below FA. (Nov 20087 set3)( (Feb08 set2)
M= { {A,B,C,D}, {0,1}, δ,C, {A,C} }
δ (A,0) = δ (A,1) = {A,B,C}
δ(B,0) = B, δ(B,1) = { A, C }
δ(C,0) = {B,C}, δ(C,1) ={ B, D }
δ (D,0) = { A, B, C, D }
δ(D,1) = {A}.
13. Design DFA to accept strings c and d such that number d’s are divisible by 4 (Nov
2008 set3)
14 Design DFA which accept the language L={0,000,00000 ……..} Over {0}(Nov
2008 set4)
15.Construct DFA for the following: (Nov 2009 set12) (Feb 2008 set3)( (Feb 2007
set4)
(a) L={w/w has both an even number of 0’s and even number of 1’s }
(b) L= { w/w is in the form of ‘x01y’ for some strings x and y consisting of 0’s
and 1’s}.
16. Construct NFAs for the following languages (Nov 2007 set1&set 3)
(a). The set of strings over alphabet {0,1,...... ,9} such that the final digit has
appeared before.
(b). The set of strings over alphabet {0,1,...... ,9} such that the final digit has
not appeared before.
(c). The set of strings of 0’s and 1’s such that there are two 0’s separated by A
number of positions that is a multiple of 4. Note that 0 is an allowable
multiple of 4.
17. Design DFA Which accept all strings which are ending with 101 over an
alphabet {0,1} Nov 2003 set 3)
Assignment:
1).Define FA. Give the mathematical representation of it and explain its significance.
2).List out various real time applications of FA.
3).Explain the difference between NFA and DFA with examples. Which one is
efficient?
Case Study :
1. Consider a real world problem and explain its solution which uses Finite Automata in an important role.
UNIT II
Finite Automata:
NFA with ε- transitions - Significance, acceptance of languages. Conversions and Equivalence: Equivalence between NFA with and without Î transitions, NFA to DFA conversion, minimization of FSM, equivalence between two FSM’s, Finite Automata with output- Moore and Melay machines.
Objective:
· To learn about the significance of ε-transitions.
· To know about the conversions in Finite Automata.
· To know about the Melay and Moore’s machines.
Topic / Lecture Date / hoursFinite Automata : NFA with ε- transitions / 1
NFA with ε- transitions / 1
NFA with ε- transitions / 1
Significance, acceptance of languages / 1
Conversions and Equivalence : Equivalence between NFA with and without Î transitions /
1
NFA to DFA conversion / 1
NFA to DFA conversion / 1
Minimization of FSM, / 1
Minimization of FSM, / 1
Equivalence between two FSM’s / 1
Finite Automata with output / 1
Moore and Melay machines. / 1
10
Applications:
· NFAs and DFAs are equivalent in that if a language is recognized by an NFA, it is also recognized by a DFA and vice versa. This equivalence is important and useful because constructing an NFA to recognize a given language is sometimes much easier than constructing a DFA for that language.
Important Questions:
1. Design a Finite State acceptor to accept the language of all binary strings that do
not include the substring 1011(May/June 2009 set 1)
2 Reduce the Moore machine: (May/June 2009 set 1)
3. What is the significance of NFA with ε-transitions? Explain. (May/June 2009 set 3)
4. Show the equivalence between NFA with and without ε-transitions. (May/June
2009 set 3)
5. Draw an equivalent deterministic finite automaton for the following automaton:
(May/June 2009 set 4)
6. Give an example of a regular language L containing Ë that cannot be accepted by
any NFA having only one accepting state, and show that your answer is correct.
(Nov 2009 set2)
7. Design a Moore Machine to determine the residue mod 4 for each binary string
treated as integer.(NOV 2008 set 1)
8. Design a Mealy machine that uses its state to remember the last symbol Read and
emits output ‘y’ whenever current input matches to previous one, and emits n
otherwise. (Nov 2008 set 1)
9. For the following NFA with €-moves convert it into an NFA without €-moves and
show that NFA with €-moves accepts the same language as shown in figure below.
(Nov 2008 set 3)(Feb 2008 set 2)(Nov 2007 set 01)
10. Design a Moore machine to determine the residue mod 5 for each binary string
treated as integer. (Feb 2008 set 1) (Nov 2007, set 4)
11. Convert the following Mealy machine into equivalent Moore machine as shown in
figure 2b. )(Nov 2004 set 1) (Nov 2005, set1 )
12. Construct DFA for given (figure 2) NFA with 2-moves (16) (Nov 2008 set 2) (Feb
2008 set 4)( NOV2007 SET 2)
14. Find NFA With out epsilon for the following diagram.
13. Minimize Finite Automata given below and show both given and reduced are
equal.(FEB 2007, SET 2) (Nov 2004 set 2)
0 1
q0 q1 q2
q1 q3 q4
q2 q5 q6
q3 q3 q4
q4 q5 q7
q5 q3 q4
q6 q5 q6
Assignment:
1).Convert the following NFA to a DFA using the method described in class. Specify
the DFA by its transition diagram. The alphabet is Σ = {0,1}.
2). Consider the following languages over Σ = {0, 1}.
· L1 is the language described by 1*(0111*)*.
· L2 is the language of strings with at least one 0 and at least two 1s.
· L3 is the language of the following NFA:
· L4 is the language described by (0 + 1)*01(0 + 1)*1.
· L5 is the language described by (011 + 101 + 110)*.
· L6 is the language of the following NFA:
· L7 is the language of all strings that do not contain 00, 010 and do not end in 0 or 01.
· (Optional) L8 is the language of the following DFA:
Which of these languages are the same and which are different? To show two languages are the same give a short argument, and to show two languages are different give a string that is in one but not in the other.(You must provide an explanation)
Case Study:
1. Explain the role of NFA and DFA in text search.
UNIT III
RegularLanguages: :
Regular sets, regular expressions, identity rules, Constructing finite Automata for a given regular expressions, Conversion of Finite Automata to Regular expressions. Pumping lemma of regular sets, closure properties of regular sets (proofs not required).
Objective:
· To learn the fundamentals for the construction finite automata.
· To know about the conversion of finite automata to regular expressions.
· To know about the pumping lemma and closure properties of regular sets.
Topic / Lecture Date / HoursRegular Languages :
Regular sets, regular expressions, identity rules, /
2
Constructing finite Automata for a given regular expressions / 1
Conversion of Finite Automata to Regular expressions / 1
Pumping lemma of regular sets / 1
Closure properties of regular sets / 1
6
Applications :
Useful in writing the expressions for the regular languages and defining properties for the expressions uses in the languages. This helps in designing the compilers.
Important Questions:
1. Given that A is regular and (A U B) is regular, does it follow that B is necessarily
regular? Justify your answer. (16m) (May/June 2009 set 1)
2. (a) Draw ε -NFA recognizing regular expression 010*+0(01+10)*11 over {0,1}
(May/June 2009 set 1)
(b) Explain Pumping lemma for regular sets. (May/June 2009 set 1)
3. (a) Define regular expression and find regular expression for the following:
L = {w | every odd position of w is a 1} defined over . = {0,1}(May/June 2009
set 1)
(b) Convert the following regular expression into NFA: (((00)*(11))U01)*
(May/June 2009 set 1)
4. (a) Convert the following finite automata to regular expressions: (May/June 2009
set 1)
(b). Using pumping lemma, show the following language is not regular:
L={w å {0,1}* | the number of 0’s in w is a perfect square}: (May/June 2009
set 1)
5. Find a Regular expression corresponding to each of the following subsets over
{0,1}*.
(a). The set of all strings containing no three consecutive 0’s.
(b). The set of all strings where the 10th symbol from right end is a 1.
(c). The set of all strings over {0,1} having even number of 0’s & odd number of