Xpert

07-28-2012, 06:56 PM

Course: Theory of Automata (3452) Semester: Spring, 2012

Level: BS (CS) Total Marks: 100

Pass Marks: 50

ASSIGNMENT No. 1

(Units: 1–4)

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 | Λ 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

(c) Context Free Language

(d) Deterministic Finite Automata

ASSIGNMENT No. 2

(Units: 5–8)

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

(c) 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.

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)

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 | Λ 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

(c) Context Free Language

(d) Deterministic Finite Automata

ASSIGNMENT No. 2

(Units: 5–8)

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

(c) 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.

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