STUPIDSID
1 (a)
Define finite automata.What are the applictaion of finite automation?
6 M
1 (b)
What are the difference between DFA and NFA?
4 M
1 (c)
Design A DFA Which Accept String of 0°s and 'I's which when interpreted as a binary integer is multiple of 5.Also Give the sequence of states that DFA is in while processing the input string:1001011.
10 M
2 (a)
Obtain the regular expression to accept string of a's, b's and c's such that fourth symbol from the right is:a and ends with :b.
4 M
2 (b)
Consider the following ?-NFA:
Computer ?-closure of each state
Convert the automation to a DFA
Computer ?-closure of each state
Convert the automation to a DFA
10 M
2 (c)
Convert the following automation to a regular expression using state elimination technique:
6 M
3 (a)
Prove that the language L={om 1n|m>n,?={0,1}is not regular.
6 M
3 (b)
Consider the DFA given by the transition diagram:
Draw the table of distinguishbilities for this automation
Construct the minimum sate equivlent DFA
Draw the table of distinguishbilities for this automation
Construct the minimum sate equivlent DFA
10 M
3 (c)
Show that if L is regualar languages ,then complement of L denoted by l is also regular
4 M
4 (a)
Define context -free grammer .Obtain the CFG for the following languages:
l={w|w €{0,1} with at least one occurrence of 101}
L={ai bj ck|i=j+k,?={a,b,c}
l={w|w €{0,1} with at least one occurrence of 101}
L={ai bj ck|i=j+k,?={a,b,c}
8 M
4 (b)
Explain the following with suitable examples:
left most derivation
Right most derivation
Parse tree
left most derivation
Right most derivation
Parse tree
6 M
4 (c)
What is an ambigous grammer? Show that grammer shown below is ambigous
S?AB|aaB
A&rarr|a
B ?b
S?AB|aaB
A&rarr|a
B ?b
6 M
5 (a)
What is an expression description of PDA? Obatin a PDA to accept the following language by final state:
L={a nb2n|n?1,?={a,b}
Draw the transmission diagram for PAD .Also show that the moves made by PDA for the string :aabbbb
L={a nb2n|n?1,?={a,b}
Draw the transmission diagram for PAD .Also show that the moves made by PDA for the string :aabbbb
12 M
5 (b)
Design a PDA for the following CFG:
S? aSb|bSa|SS|?
S? aSb|bSa|SS|?
8 M
6 (a)
What is an unit production? Begin with the grammar: S→ABC|BaB
A →aA|BaC|aaa
B→bBb|a|D
D→ ε
Eliminate ε - productions
Eliminate any unit production in the resulting grammar
Eliminate any useless symbol in the resulting grammar.
A →aA|BaC|aaa
B→bBb|a|D
D→ ε
Eliminate ε - productions
Eliminate any unit production in the resulting grammar
Eliminate any useless symbol in the resulting grammar.
10 M
6 (b)
Obatain the following grammer in CNF.
S ?0A|1B
A ?0AA|1S|1
B ?1BB |0s|0
S ?0A|1B
A ?0AA|1S|1
B ?1BB |0s|0
10 M
7 (a)
Define a turning machine .Expain how the machine would be desined to simulate a computer
8 M
7 (b)
Design a turning machine to accept the set of all palinadromes over {0,1}.Also ,indicates the moves made by Turnig machine for the string :1001.
12 M
Write short note on:
8 (a)
universal machine
5 M
8 (b)
Post correspondance problem
5 M
8 (c)
Halting problem of TM
5 M
8 (d)
Recursive language
5 M
More question papers from Formal Languages and Automata Theory