Assignment GDB Solution: CS402 Theory of Automata


CS402 Assignment 2 Solution Fall 2017

Question No 1:                                                                                                                 Marks:5+5=10 Construct a regular expression defining each of the following languages over the alphabet ∑={a      b}: a)      All words without the pattern ‘bb’ in them. b)      All words that ends with a or bbbb   Question No 2:                                                                                                                           Marks=5 Build an FA that accepts the language of all words over the […]

CS402 GDB Solution Spring 2017

The GDB will remain open for two days (48 hours). You may submit your GDB from “July 20, 2017 To July 21, 2017, 11:59 PM”. GDB Topic:  “What comes to your mind in terms of automata theory when we talk about CPU and Computer? Justify your answer with scientific reason(s)

CS402 Assigment 3 Solution Spring 2017

Question No. 01 (Marks: 10 ) Draw the FA for language Lc (complement of L) and let L be the language over the alphabet Σ = {0, 1}, consisting of only two words “010” and “011”. Solution : Question No. 02 (Marks: 10 ) Consider the language L which is EVEN-EVEN, defined over Σ = […]

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 […]