07-28-2012, 06:56 PM
Course: Theory of Automata (3452) Semester: Spring, 2012
Level: BS (CS) Total Marks: 100
Pass Marks: 50
Note: All questions are compulsory. All questions carry equal marks.
Q. 1 (a) Explain the following terms:
i) Automata
ii) Set theory
(b) For the following relations between sets A and B mention if they are one to one and/or onto: A = {a, b, c} B = {1, 2, 3}
i) {(a, 1), (b, 1), (c, 1)}
ii) {(a, 2), (b, 2), (c, 2)}
iii) {(a, 1), (a, 2), (b, 2), (c, 3)}
iv) {(a, 2), (b, 1), (c, 2)}
Q. 2 (a) Consider the language S*, where S= {aa b}. How many words does this language have of length 4? Of length 5? What can be said in general?
(b) Construct a regular expression defining each of the following languages over the alphabet ∑ = {a b}:
i) All words in which a appears tripled, if at all. This means that every clump of a’s contains 3 or 6 or 9 or 12… a’s.
ii) All strings that have exactly one double letter in them.
iii) All words that contain exactly two b’s or exactly three b’s, not more.
Q. 3 (a) What is the relationship between regular languages and context free grammars? Discuss them? Construct a language that can be generated by CFG.
(b) Consider the Context Free Grammar
S à a X X à a x | b X | [FONT="]Λ [/FONT]Y à b b b
(a +b) * b b b (a + b) *
Q. 4 (a) Construct an example DFA? Write down the steps to convert FA into DFA.
(b) Construct DFA for the following regular expression: (a / b) * a b *.
Q. 5 Define and explain the following terms.
(a) Context Free Grammar
(b) Regular Expression
© Context Free Language
(d) Deterministic Finite Automata
Total Marks: 100 Pass Marks: 50
Q. 1 (a) What is a regular language? How it can be differentiated from a non-regular language?
(b) Show whether the language (0^p 1^100) for all integer p, with 0<p<100, is a regular language or a non-regular language.
Q. 2 (a) Define and explain Push Down Automata with the help of a suitable example.
(b) Write a Push Down Automaton to accept the langue {0^n 1^n 0^m 1^m, for all n,m>=0.
Q. 3 Explain the following terms with suitable examples:
(a) Greibach Normal Form
(b) Chomsky Normal Form
© Closure properties of Regular Languages
(d) Non-Deterministic Finite Automata
Q. 4 Define and explain the term parsing with the help of a suitable example. Discuss the types of parsing in detail.
Q. 5 What is standard turing machine? Explain with the help of examples.
[FONT="]
[/FONT] 3452 Theory of Automata Credit Hours: 3 (3+0)
Recommended Book:
Introduction to Computer Theory by Denial I. A. Cohen
Course Outlines:
Unit No. 1 Mathematical Preliminaries
Set theory, Relations and Functions, Recursive Definitions, Directed Graphs and Mathematics
Unit No. 2 Languages
Strings and Languages, Finite Specification of Languages, Regular Sets and Expression
Unit No. 3 Context-Free Grammars
Context-free Grammars and Languages, Regular Grammar and Arithmetic Expression
Unit No. 4 Parsing
Leftmost Deviations and Ambiguity, Regular Grammars, Bottom-up Parsing shift Reducer Parser.
Unit No. 5 Normal Forms
Elimination of Lambda Chain Rules, Chomsky Normal Form, Greibach Normal Form
Unit No. 6 Finite Automata
Finite State Machine, Deterministic Finite Automata, Nondeterministic Finite Automata, Lambda Transitions, Expression Graphs
Unit No.7 Regular Languages
Regular Grammar and Finite Automate, Non-regular Language, Pumping Lemma for Regular Language, Closure Properties of Regular Languages
Unit No. 8 Pushdown Automata and Context-free Languages
Pushdown Automata, Push Down Automata and Context-free Language, Pumping Lemma for Context-Free Languages.
Unit No. 9 Turing Machine
Standard Turing Machine, Multiple Machines, Nondeterministic, Turing Machines
Level: BS (CS) Total Marks: 100
Pass Marks: 50
ASSIGNMENT No. 1
(Units: 1–4)
Q. 1 (a) Explain the following terms:
i) Automata
ii) Set theory
(b) For the following relations between sets A and B mention if they are one to one and/or onto: A = {a, b, c} B = {1, 2, 3}
i) {(a, 1), (b, 1), (c, 1)}
ii) {(a, 2), (b, 2), (c, 2)}
iii) {(a, 1), (a, 2), (b, 2), (c, 3)}
iv) {(a, 2), (b, 1), (c, 2)}
Q. 2 (a) Consider the language S*, where S= {aa b}. How many words does this language have of length 4? Of length 5? What can be said in general?
(b) Construct a regular expression defining each of the following languages over the alphabet ∑ = {a b}:
i) All words in which a appears tripled, if at all. This means that every clump of a’s contains 3 or 6 or 9 or 12… a’s.
ii) All strings that have exactly one double letter in them.
iii) All words that contain exactly two b’s or exactly three b’s, not more.
Q. 3 (a) What is the relationship between regular languages and context free grammars? Discuss them? Construct a language that can be generated by CFG.
(b) Consider the Context Free Grammar
S à a X X à a x | b X | [FONT="]Λ [/FONT]Y à b b b
(a +b) * b b b (a + b) *
Q. 4 (a) Construct an example DFA? Write down the steps to convert FA into DFA.
(b) Construct DFA for the following regular expression: (a / b) * a b *.
Q. 5 Define and explain the following terms.
(a) Context Free Grammar
(b) Regular Expression
© Context Free Language
(d) Deterministic Finite Automata
ASSIGNMENT No. 2
(Units: 5–8)
Q. 1 (a) What is a regular language? How it can be differentiated from a non-regular language?
(b) Show whether the language (0^p 1^100) for all integer p, with 0<p<100, is a regular language or a non-regular language.
Q. 2 (a) Define and explain Push Down Automata with the help of a suitable example.
(b) Write a Push Down Automaton to accept the langue {0^n 1^n 0^m 1^m, for all n,m>=0.
Q. 3 Explain the following terms with suitable examples:
(a) Greibach Normal Form
(b) Chomsky Normal Form
© Closure properties of Regular Languages
(d) Non-Deterministic Finite Automata
Q. 4 Define and explain the term parsing with the help of a suitable example. Discuss the types of parsing in detail.
[FONT="]
[/FONT] 3452 Theory of Automata Credit Hours: 3 (3+0)
Recommended Book:
Introduction to Computer Theory by Denial I. A. Cohen
Course Outlines:
Unit No. 1 Mathematical Preliminaries
Set theory, Relations and Functions, Recursive Definitions, Directed Graphs and Mathematics
Unit No. 2 Languages
Strings and Languages, Finite Specification of Languages, Regular Sets and Expression
Unit No. 3 Context-Free Grammars
Context-free Grammars and Languages, Regular Grammar and Arithmetic Expression
Unit No. 4 Parsing
Leftmost Deviations and Ambiguity, Regular Grammars, Bottom-up Parsing shift Reducer Parser.
Unit No. 5 Normal Forms
Elimination of Lambda Chain Rules, Chomsky Normal Form, Greibach Normal Form
Unit No. 6 Finite Automata
Finite State Machine, Deterministic Finite Automata, Nondeterministic Finite Automata, Lambda Transitions, Expression Graphs
Unit No.7 Regular Languages
Regular Grammar and Finite Automate, Non-regular Language, Pumping Lemma for Regular Language, Closure Properties of Regular Languages
Unit No. 8 Pushdown Automata and Context-free Languages
Pushdown Automata, Push Down Automata and Context-free Language, Pumping Lemma for Context-Free Languages.
Unit No. 9 Turing Machine
Standard Turing Machine, Multiple Machines, Nondeterministic, Turing Machines