# CS402 Assignment 2 Solution Spring 2018

Question No 1:                                                                                                                 Marks:5 Build a transition table and transition diagram corresponding to r* where r=a(a+b)*. Question No 2:                                                                                                   Marks=5+5=10 Draw the GTG for the following language. Language L of strings, defined over Σ = {x, y}, beginning with and ending in same letters. Write down its regular expression too.

# CS402 Assignment 1 Solution Spring 2018

Question No 1: Marks:5 Construct a regular expression (RE) defining each of the following languages over the alphabet ∑={a b}: All words ends in 3 consecutive b. All words having at least one ‘a’ Question No 2: Marks=5+5=10 Construct an FA which recognizes the set of all strings defined over S = {x, y} starting […]

# CS402 Assignment 2 Solution Fall 2017

Question No 1:                                                                                                              Marks:5+5+5=15 Consider the following two regular languages: Let L1 be the language defined over alphabet ∑={a    b} that contains all strings starting with alphabet a. (Example strings abbababa, aaaab, abaabbbb) Let L2 be the language defined over alphabet ∑={a    b} that contains all strings in which alphabet a comes in the string in even number. (Example […]

# 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 Spring 2014

If we would require to implement chess game, what would be the suggested automata / machine from the list given below. Also provide reason(s) in 2 – 3 lines to support your choice. 1 – FA 2 – NFA 3 – TG 4 – TM 5 – Derivation Tree Solution: For Chess game we use FA. because Chess game have […]