STUPIDSID
IT
1(a)
What is the complement of the language accepted by the NFA shown below? Assume S={a} and c is the empty string.
2 M
1(b)
Definition of a language L with alphabet {a} is given as following
{ an k | k > 0, and n is a positive integer constant }
What is the minimum number of states needed in a DFA to recognize L?
{ an k | k > 0, and n is a positive integer constant }
What is the minimum number of states needed in a DFA to recognize L?
2 M
1(c)
What is Multi-Tape Turing Machine?
3 M
1(d)
Design Mealy Machine to convert each occurrence of substring 1000 by 1001.
7 M
1(e)
State that whether a following Language is Regular or not.
1) L = {WWR | |W|=2 over ∑={a,b}}
2) L = {WWR | Wc (a,b)*}
1) L = {WWR | |W|=2 over ∑={a,b}}
2) L = {WWR | Wc (a,b)*}
6 M
2(a)
Give formal definition of a Turing Machine.
5 M
2(b)
Write a regular expression for the following languages, over sigma=(a,b}.
1. Seventh symbol from right must be a.
2. Every second character is b.
3. Exactly one ab.
1. Seventh symbol from right must be a.
2. Every second character is b.
3. Exactly one ab.
10 M
2(c)
Explain Chomsky Hierarchy.
5 M
3(a)
Construct a TM for accepting Even palindromes.
10 M
3(b)
Design PDA For recognizing L={an b2 n+1 | n>=1}
10 M
4(a)
Convert the following grammar to Chomsky Normal Form. Show all the relevant steps briefly.
S --->bA | aB
A --->bAA | aS | a
B ---> aBB | bS | b
S --->bA | aB
A --->bAA | aS | a
B ---> aBB | bS | b
10 M
4(b)
Give the technical strategy to convert CFG to GNF.
Convert the following grammar to GNF.
S → AA | a
A → SS | b
Convert the following grammar to GNF.
S → AA | a
A → SS | b
10 M
5(a)
Enumerate the differences between finite automata and non-deterministic automata?
8 M
5(b)
Construct NFA, DFA for the regular Expression R=ab(a+b)+abb. Obtain minimized DFA.
7 M
5(c)
Give formal definition of a Push Down Automata(PDA).
5 M
Write short note on
6(a)
Unsolvable problems
10 M
6(b)
Recursive and Recursively enumerable languages.
10 M
6(c)
Simplification of CFG.
10 M
More question papers from Automata Theory