formal languages and automata theory online bits

Code No: 07A50501 Set No. 1
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
III B.Tech. I Sem., II Mid-Term Examinations, November– 2009
FORMAL LANGUAGES AND AUTOMATA THEORY
Objective Exam
Answer All Questions. All Questions Carry Equal Marks. Time: 20 Min. Marks: 20.
I. Choose the correct alternative:
1. ____is used for describing block structure in programming languages. [ ]
a)Context free Language b)Context sensitive c)procedural d)primitive references.
2. The derivation of CFG can be represented by______ [ ] a)graphs b)definitions. c)trees d)grammar
3. The yield of a derivation tree is the _______the labels of the leaves without related petition of the left –to-right ordering.. [ ]
a)union b)cancatination c)sequence d)join
4. The following CFG is equivalent of the RE S->aS/bS/a/b_____ [ ]
a)(a+b) b)(a+b)* c)(a+b)(a+b) d)all of these
5. If G is a Context free Grammar, we can find a context Free Grammar G1,which has no null
Productions or unit productios such that ____ [ ]
a)G1=G b)L(G1)=L(G) c)G(L)=G1(L) d)L=G.
6. In turing Machine directed edges are used to represent ______ [ ]
a)final state b)initial state c)trasition function d)transition of states.
7. _______is used to restrict the Length of the Tape in Turing machines. [ ]
a)finite Automation b)Deterministic Automaton
c)Non Linear Automaton d)Linear Bounded Automaton
8. In NP Completeness for defining P we require the______ [ ]
a)space complexity b)input strings c)time complexity d)Grammar
9. ____________ can be thought of as a Finite state automaton connected to R/W head [ ]
a)pumping Lemma b)turing machine
c)Finite Deterministic automaton d)Recursive Functions
10. In the Turing Machine each cell can store ____No of inputs as symbols. [ ]
a)finite b)Null c)one d)infinite
Cont…..[2]

A
[2]
Code No: 07A50501 Set No. 1
II. Fill in the Blanks:
11. _______ is a process of splitting a sentence into words.
12. ______________ is used to restrict the Length of the Tape.
13. Turing and church independently designed a computing machine which can carry out a ________
14. The class of Automata that can be associated with context free language _________
15. Type 0 language accepted by ________
16. A terminal symbol ω belongs c(G) is ____________ if there exists more than one, derivation trees
for ω
17. A language L is in the class ______ if there exists a Non-deterministic TMM, such that M has time complexity p(n) for some polynomial P and M accepts L.
18. Context sensitive Language accepted by ______________
19. A string of symbols obtained by reading the leaves of the tree from left to right,omitting any €’s
encountered is called ______
20. A variable may be _______ if there is no way of getting the terminal from it.
-oOo-
Code No: 07A50501 Set No. 2
FORMAL LANGUAGES AND AUTOMATA THEORY
Objective Exam
Name:______________________________ Hall Ticket No.
Answer All Questions. All Questions Carry Equal Marks. Time: 20 Min. Marks: 20.
I. Choose the correct alternative:
1. The following CFG is equivalent of the RE S->aS/bS/a/b_____ [ ]
a)(a+b) b)(a+b)* c)(a+b)(a+b) d)all of these
2. If G is a Context free Grammar, we can find a context Free Grammar G1,which has no null
Productions or unit productios such that____ [ ]
a)G1=G b)L(G1)=L(G) c)G(L)=G1(L) d)L=G.
3. In turing Machine directed edges are used to represent ______ [ ]
a)final state b)initial state c)trasition function d)transition of states.
4. _______is used to restrict the Length of the Tape in Turing machines. [ ]
a)finite Automation b)Deterministic Automaton
c)Non Linear Automaton d)Linear Bounded Automaton
5. In NP Completeness for defining P we require the______ [ ]
a)space complexity b)input strings c)time complexity d)Grammar
6. ____________ can be thought of as a Finite state automaton connected to R/W head [ ]
a)pumping Lemma b)turing machine
c)Finite Deterministic automaton d)Recursive Functions
7. In the Turing Machine each cell can store ____No of inputs as symbols. [ ]
a)finite b)Null c)one d)infinite
8. ____is used for describing block structure in programming languages. [ ]
a)Context free Language b)Context sensitive c)procedural d)primitive references.
9. The derivation of CFG can be represented by______ [ ] a)graphs b)definitions. c)trees d)grammar
10. The yield of a derivation tree is the _______the labels of the leaves without related petition of the left –to-right ordering [ ]
a)union b)cancatination c)sequence d)join
Cont…..[2]

A
[2]
Code No: 07A50501 Set No. 2
II. Fill in the Blanks:
11. The class of Automata that can be associated with context free language _________
12. Type 0 language accepted by ________
13. A terminal symbol ω belongs c(G) is ____________ if there exists more than one, derivation trees
for ω
14. A language L is in the class ______ if there exists a Non-deterministic TMM, such that M has time complexity p(n) for some polynomial P and M accepts L.
15. Context sensitive Language accepted by ______________
16. A string of symbols obtained by reading the leaves of the tree from left to right,omitting any €’s
encountered is called ______
17. A variable may be _______ if there is no way of getting the terminal from it.
18. _______ is a process of splitting a sentence into words.
19. ______________ is used to restrict the Length of the Tape.
20. Turing and church independently designed a computing machine which can carry out a ________
-oOo-
Code No: 07A50501 Set No. 3
FORMAL LANGUAGES AND AUTOMATA THEORY
Objective Exam
Name:______________________________ Hall Ticket No.
Answer All Questions. All Questions Carry Equal Marks. Time: 20 Min. Marks: 20.
I. Choose the correct alternative:
1. In turing Machine directed edges are used to represent ______ [ ]
a)final state b)initial state c)trasition function d)transition of states.
2. _______is used to restrict the Length of the Tape in Turing machines. [ ]
a)finite Automation b)Deterministic Automaton
c)Non Linear Automaton d)Linear Bounded Automaton
3. In NP Completeness for defining P we require the______ [ ]
a)space complexity b)input strings c)time complexity d)Grammar
4. ____________ can be thought of as a Finite state automaton connected to R/W head [ ]
a)pumping Lemma b)turing machine
c)Finite Deterministic automaton d)Recursive Functions
5. In the Turing Machine each cell can store ____No of inputs as symbols. [ ]
a)finite b)Null c)one d)infinite
6. ____is used for describing block structure in programming languages. [ ]
a)Context free Language b)Context sensitive c)procedural d)primitive references.
7. The derivation of CFG can be represented by______ [ ] a)graphs b)definitions. c)trees d)grammar
8. The yield of a derivation tree is the _______the labels of the leaves without related petition of the left –to-right ordering [ ]
a)union b)cancatination c)sequence d)join
9. The following CFG is equivalent of the RE S->aS/bS/a/b_____ [ ]
a) (a+b) b) (a+b)* c) (a+b)(a+b) d) all of these
10. If G is a Context free Grammar, we can find a context Free Grammar G1,which has no null
Productions or unit productios such that ____ [ ]
a) G1=G b) L(G1)=L(G) c) G(L)=G1(L) d) L=G.
Cont…..[2]

A
[2]
Code No: 07A50501 Set No. 3
II. Fill in the Blanks:
11. A terminal symbol ω belongs c(G) is ____________ if there exists more than one, derivation trees
for ω
12. A language L is in the class ______ if there exists a Non-deterministic TMM, such that M has time complexity p(n) for some polynomial P and M accepts L.
13. Context sensitive Language accepted by ______________
14. A string of symbols obtained by reading the leaves of the tree from left to right,omitting any €’s
encountered is called ______
15. A variable may be _______ if there is no way of getting the terminal from it.
16. _______ is a process of splitting a sentence into words.
17. ______________ is used to restrict the Length of the Tape.
18. Turing and church independently designed a computing machine which can carry out a ________
19. The class of Automata that can be associated with context free language _________
20. Type 0 language accepted by ________
-oOo-
Code No: 07A50501 Set No. 4
FORMAL LANGUAGES AND AUTOMATA THEORY
Objective Exam
Name:______________________________ Hall Ticket No.
Answer All Questions. All Questions Carry Equal Marks. Time: 20 Min. Marks: 20.
I. Choose the correct alternative:
1. In NP Completeness for defining P we require the______ [ ]
a)space complexity b)input strings c)time complexity d)Grammar
2. ____________ can be thought of as a Finite state automaton connected to R/W head [ ]
a)pumping Lemma b)turing machine
c)Finite Deterministic automaton d)Recursive Functions
3. In the Turing Machine each cell can store ____No of inputs as symbols. [ ]
a)finite b)Null c)one d)infinite
4. ___is used for describing block structure in programming languages. [ ]
a)Context free Language b)Context sensitive c)procedural d)primitive references.
5. The derivation of CFG can be represented by______ [ ] a)graphs b)definitions. c)trees d)grammar
6. The yield of a derivation tree is the _______the labels of the leaves without related petition of the left –to-right ordering [ ]
a)union b)cancatination c)sequence d)join
7. The following CFG is equivalent of the RE S->aS/bS/a/b_____ [ ]
a)(a+b) b)(a+b)* c)(a+b)(a+b) d)all of these
8. If G is a Context free Grammar, we can find a context Free Grammar G1,which has no null
Productions or unit productios such that____ [ ]
a)G1=G b)L(G1)=L(G) c)G(L)=G1(L) d)L=G.
9. In turing Machine directed edges are used to represent ______ [ ]
a)final state b)initial state c)trasition function d)transition of states.
10. _______is used to restrict the Length of the Tape in Turing machines. [ ]
a)finite Automation b)Deterministic Automaton
c)Non Linear Automaton d)Linear Bounded Automaton
Cont…..[2]

A
[2]
Code No: 07A50501 Set No. 4
II. Fill in the Blanks:
11. Context sensitive Language accepted by ______________
12. A string of symbols obtained by reading the leaves of the tree from left to right,omitting any €’s
encountered is called ______
13. A variable may be _______ if there is no way of getting the terminal from it.
14. _______ is a process of splitting a sentence into words.
15. ______________ is used to restrict the Length of the Tape.
16. Turing and church independently designed a computing machine which can carry out a _________
17. The class of Automata that can be associated with context free language _________
18. Type 0 language accepted by ________
19. A terminal symbol ω belongs c(G) is ____________ if there exists more than one, derivation trees
for ω.
20. A language L is in the class ______ if there exists a Non-deterministic TMM, such that M has time complexity p(n) for some polynomial P and M accepts L.