Assignment GDB Solution: CS402 Theory of Automata


CS402 GDB Solution Feb 2015

GDB Topic: Can Push Down Automaton (PDA) with n-stacks be equally powerful to a Turing machine while dealing Context Free Languages (CFG)? Justify your point of view with logical reasons in either case. Solution:  Yes it is true, Turing machines are more powerful than PDAs. The easiest example would be to show that Turing machines can […]

CS402 Theory of Automata Assignment 2 Solution Fall 2014

Q.1: Consider the following Regular Expression (RE): zx(y + z)* x (x + y+ z)*y + zy(x + z)* x (x + y+ z)*y + zz(x + y)* x (x + y+ z)*y Draw transition graph for the above RE.                                    […]

CS402 Theory of Automata Assignment 1 Solution Fall 2014

Q.1. Write a Regular Expression (RE) for the language of all strings defined over Σ = {x, y, z} which begins with z, x in the middle and ends with y. The minimum length of all strings must be 4. [Marks 6] Q.2. a) Make a transition table for RE in Q.1. b) Draw a […]

CS402 Theory of Automata GDB Solution Fall 2013

PDA’s are effective tool to represent palindrome as compared to CFG’s.?  give 4-5 line comments in favor or against this. Solution: In the automata theory, a set of all palindromes in a given alphabet is a typical example of a language that is context-free grammar (CFG), but not regular. This means that it is impossible for a computer with a finite amount of memory to reliably test for […]

CS402 Theory of Automata Non Graded Assignment 3 Fall 2013

Q1:  [Marks = 8]   Consider Moore Machine, Draw equivalent Mealy Machine. [Show step by step process for each state]   Q2: [Marks = 12 = 4 + 8] Determine the relations for new state transitions and then construct Transition Table for mealy machine of the given sequential circuit.

CS402 Theory of Automata Assignment 1 Solution Fall 2013

Assignment No. 1 Semester: Fall 2013 CS402 – Theory of Automata   Instructions Please read the following instructions carefully before submitting assignment: It should be clear that your assignment will not get any credit if:   Assignment is submitted after due date. Submitted assignment does not open or file is corrupt. Assignment is copied (From internet/ to […]

CS402 Theory of Automata Assignment 1 Solution Spring 2013

Assignment Question 1: [Marks: 10] Σ = {a, b} Write a Regular Expression, that only accepts strings with exactly two or three a’s in the string. There is no restriction on occurrence of b’s in the string. Few examples of accepted strings are as under; – bbaabbbba – baba – aba – abaa – aa – aaa etc. Solution: a, […]