Flat Mid2 CSW

Department of Computer Engineering (SE)
Subject: FORMAL LANGUAGES AND AUTOMATA THEORY
II MID –EXAMINATION QUESTION PAPER
II Year Sem-II BRANCH - CSW
Prepared by: Mrs. S.Hymavathi
SET-1
1. Construct a PDA to accept the language L ={a n b2n | n >= 1} by a final state. Draw
the graphical representation of the PDA. Also show the moves made by the PDA for the
string aaabbbbbb. ?
2. Construct a Turing Machine that accepts the language L = {0 n1n | n ≥1}. Give the
transition diagram for the Turing Machine obtained and also show the moves made by the
Turing machine for the string 000111. ?
3. Explain about post correspondence problem?
4. Write the closure properties and decision properties of CFL?
5. Construct the CFG for the PDA M =({q0,q1}, {0,1}, {R,Z0}, δ, q0, Z0, Φ )
And δ is given by
δ(q0,1,Z0)=(q0,RZ0)
δ(q0,1,R)=(q0,RR)
δ(q0,0,R)=(q1,R)
δ(q1,0, Z0)=(q0, Z0)
δ(q0,ε, Z0)=(q0,ε)
δ(q1,1,R)=(q1,ε)
6. Give an overview of recursively enumerable languages?

SET-2
1. Use the following grammar:

S->ABC | BbB,
A->aA | BaC|aaa
B->bBb| a|D
C->CA|AC
D-> ε
a) Eliminate ε-productions.
b) Eliminate any unit productions in the resulting grammar.
c) Eliminate any useless symbols in the resulting grammar.
2. Construct a Turing Machine that accepts the language L = {anbncn| n ≥1}. Give the
transition diagram for the Turing Machine obtained?
3. Explain about the Halting problem?
4. Find the GNF equivalent to the following
S → AA | 0
A → SS | 1
5. Discuss briefly about decidability and undecidability problem?
6. Construct the PDA for the following grammar:
S→aAA, A→aS | bS | a
SET-3
1. Discuss the Pumping lemma for Context Free Languages concept with example?
2. Construct a Turing Machine that accepts the language L = {WcWR| W in (a+b) *}. ?
3 Construct a PDA to accept the following language L= {anbn/n>0} ?
4. Convert the following grammar into CNF.
S aSa | bSb | a | b | aa | bb
5. Explain the importance of Turing Machines and also give descriptions of various types
of Turing Machines with necessary examples ?
6. What is decidability? Explain in brief about any two undecidable problems ?

UNIT-3
1. Context free grammar is__________
a)Compiler
b) Language expression
c) Language translator
d) None of the above
2. context free Grammar is Closed Under________
a) Union
b) Kleen star
c) Concatenation
d) All of the above
3. The instantaneous description of PDA shows____

a) Present state
b) Stack symbol
c) String to be processed
d) All of these
4 A PDA behaves like FA when the number of auxiliary Memory it has is

a) 0
b) 1
c) 3
d) None
5. Derivation tree is________
a) Parse tree
b) Syntax tree
c) Both a and b
d) None
1. CFG stands for________________

2. The PDA accepts a string when __________ is empty
3. Ambiguous if grammar ___________
4. The moves in the PDA is technically termed as:____________
5. The operations performed on the PDA is _______
UNIT-4
1. Which of the following relates to Chomsky hierarchy?

a) Regular<CFL<CSL<Unrestricted
b) CFL<CSL<Unrestricted<Regular
c) CSL<Unrestricted<CF<Regular
d) None of the mentioned
Which of the following is an incorrect regular expression identity?

a) R+f=R
b) eR=e
c) Rf=f
2. Which of the following strings is not generated by the given grammar:

S->SaSbS|e
a) aabb
b) abab
c) abaabb
3. Context free grammar is called Type 2 grammar because of ______________

hierarchy.
a) Greibach
b) Backus
c) Chomsky
d) None of the mentione
4. Let G=(V, T, P, S)
where a production can be written as:
S->aAS|a
A->SbA|ba|SS
Which of the following string is produced by the grammar?
a) aabbaab
b) aabbaa
c) baabab
5. abb*c denotes which of the following?
a) {a bn c|n=0}
b) {ab n c|n>=1}
c) {a n bc|n=0}
d) {abcn |n>0}
6. There exists a Context free grammar such that:

X->aX
Which among the following is correct with respect to the given assertion?
a) Left Recursive Grammar
b) Right Recursive Grammar
c) Non Recursive Grammar
7. Which among the following is a unit Production

a) A-> BB
b) A->B
c) A->BC
d) All of the above
8. The CNF is_____

a)non terminal-> non terminal. Non terminal
b) non terminal-> terminal. non terminal
c) non terminal-> non terminal
d) non of the above
10 To simplify a CFG , WE CAN SKIP the following grammar

a) Removal of null production
b) Removal of Unit productions
c) Removal of Useless symbol
1. L->rLt|tLr|t|r The given grammar produces a language which is_______________
2. A Turing machine operates over_____________memory.
3. The ability for a system of instructions to simulate a Turing Machine is called _________
4. Turing machine can be represented by using the tools__________

5. If d is not defined on the current state and the current tape symbol, then the machine
______
6. The class of recursively enumerable language is known as__________
7. A multitapeTuring machine is ________ powerful than a single tape Turing machine.
8. In a n-track Turing machine, _________ head/heads read and write on all tracks
simultaneously.
9. ___________ is used to prove the language is not context free
10. Expand GNF___________
UNIT- 5
1. Enumerator is a Turing machine with __________

a) an output printer
b) 5 input tapes
c) a stack
d) none of the mentioned
2. A recursive language is also called

a) Decidable
b) Undecidable
c) Both (a) and (b)
d) None of these
3. Which of the problems are unsolvable?

a) Halting problem
b) Boolean Satisfiability problem
c) Both (a) and (b)
4. A PCP problem is solvable if

a) |∑| = 1
b) |∑| = 4
c) |∑| = 2
d) None of these
5. Which of the following are the models equivalent to Turing machine?
a) Multi tape Turing machine
b) Multi track Turing machine
c) Register machine a
d) All of the mentioned
6. PCP having no solution is called

a. undecidability of PCP
b. decidability of PCP
c. Semi-decidability of PCP
d. d None
7. Which of the following is type- 2 grammar?

a. A→ α where A is terminal
b. A→ α where A is Variable
c. Both
d. None
8. If every string of a language can be determined whether it is legal or illegal in finite

time the language is called
a. Decidable
b.undecidable
c.Interpretive
d. Non deterministic
9. A Problem is called __________ if its has an efficient algorithm for it self
a) tractable
b) intractable
c)computational
d)none of the mentioned
10. IF PCP is decidable then MPCP is ______
a) decidable
b) undecidable
c)can’t say
d) none
1. A Turing machine that has the length of its tape limited to the length of the input string
then the language is called as___________
2. Halting problem is also called as__________________
3. A DTM is a seven-tuple: M = (Q, Σ, Γ, δ, q0, B, F) in this what is B____________
4. PCP stands for____________
5. A language L is said to be ____________ if there is a Turing machine M such that

L(M)=L and M halts at every point
6. The language accepted by a Turing machine is called ____________
7. Decidable can be taken as a synonym to_____________
8. algorithm is called efficient if it runs in ____________ time on a serial computer.
9. The set of all recursively enumerable languages is____________
10. The complement of recursive language is _______________

Flat Mid2 CSW

Uploaded by

Copyright:

Available Formats

Flat Mid2 CSW

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Flat Mid2 CSW

Uploaded by

Copyright:

Available Formats

Department of Computer Engineering (SE)

Subject: FORMAL LANGUAGES AND AUTOMATA THEORY

II MID –EXAMINATION QUESTION PAPER

II Year Sem-II BRANCH - CSW

Prepared by: Mrs. S.Hymavathi

6. Give an overview of recursively enumerable languages?

1. Use the following grammar:

3 Construct a PDA to accept the following language L= {anbn/n>0} ?

4. Convert the following grammar into CNF.

of Turing Machines with necessary examples ?

6. What is decidability? Explain in brief about any two undecidable problems ?

1. Context free grammar is__________

2. context free Grammar is Closed Under________

3. The instantaneous description of PDA shows____

4 A PDA behaves like FA when the number of auxiliary Memory it has is

5. Derivation tree is________

1. CFG stands for________________

1. Which of the following relates to Chomsky hierarchy?

Which of the following is an incorrect regular expression identity?

2. Which of the following strings is not generated by the given grammar:

3. Context free grammar is called Type 2 grammar because of ______________

6. There exists a Context free grammar such that:

7. Which among the following is a unit Production

8. The CNF is_____

10 To simplify a CFG , WE CAN SKIP the following grammar

1. L->rLt|tLr|t|r The given grammar produces a language which is_______________

2. A Turing machine operates over_____________memory.

4. Turing machine can be represented by using the tools__________

6. The class of recursively enumerable language is known as__________

7. A multitapeTuring machine is ________ powerful than a single tape Turing machine.

9. ___________ is used to prove the language is not context free

10. Expand GNF___________

1. Enumerator is a Turing machine with __________

2. A recursive language is also called

3. Which of the problems are unsolvable?

4. A PCP problem is solvable if

6. PCP having no solution is called

7. Which of the following is type- 2 grammar?

8. If every string of a language can be determined whether it is legal or illegal in finite

9. A Problem is called __________ if its has an efficient algorithm for it self

d)none of the mentioned

10. IF PCP is decidable then MPCP is ______

2. Halting problem is also called as__________________

3. A DTM is a seven-tuple: M = (Q, Σ, Γ, δ, q0, B, F) in this what is B____________

4. PCP stands for____________

5. A language L is said to be ____________ if there is a Turing machine M such that

6. The language accepted by a Turing machine is called ____________

7. Decidable can be taken as a synonym to_____________

8. algorithm is called efficient if it runs in ____________ time on a serial computer.

9. The set of all recursively enumerable languages is____________

10. The complement of recursive language is _______________

You might also like