FLAT - MID-I-BITS (UNITI,II)

FLAT I-MID-BITS-UNIT-I,II

 

UNIT-I-OBJECTIVE QUESTIONS (PART-I)

1. Which of the following string  has length 0 ?

            ( a) s      ( b ) a       ( c ) a b c         ( d ) ∈

2. If  ∑={a} then ∑^*=

( a) { ∈ , a , a a }    ( b ) { ∈ }      ( c ) { a , a a - - - - - - }       ( d ) { ∈ , a , a a , - - - - }

3. A  grammar is a device

            ( a) acceptor   ( b ) generative     ( c ) cognitive      ( d ) can ’t say

4. In transition diagrams a state pointed by an arrow represents the state.

            ( a) final or start    ( b ) interior    ( c ) final      ( d ) start

5. NFA stands for

            ( a) Nondeterministic finite automation      ( b ) Nondeterministic finite analysis

            ( c ) Nondeterministic finite authorization    ( d ) Nondeterministic finite acceptance

6. ___________ is set of strings.

(a)   Language

(b)   Grammar

(c)    String

(d)   NFA

7. The basic limitation of FSM is that __________.

(a)   It can’t remember arbitrary large amount of Information.

(b)   It sometimes fails to recognize grammars that are not regular.

(c)    It sometimes fails to recognize grammars that are  regular.

(d)   It can remember arbitrary large amount of Information.

8. Application of Finite Automation is ______________.

(a)   Lexical Analyzer

(b)   Parser

(c)    Scanner

(d)   Semantic Analyzer

9. An FSM can be used to add two given Integer. That is _________.

(a)   True

(b)   False

(c)    May be true

(d)   Can’t say

10. We formally denote a finite automation by a __________ tuple.

(a)   2

(b)   4

(c)    5

(d)   6

11. We formally denote a finite automation by (Q,∑, δ,q_0,F) where ∑ is________.

(a)   A finite set of states.

(b)   Input alphabet.

(c)    Initial state.

(d)   Final State.

12. Finite State Machine ___________ recognize palindrome.

(a)   Can

(b)   Can’t

(c)    May

(d)   May not

13. In transition diagrams sate are represented by _________.

(a)   Ellipse

(b)   Circles

(c)    Triangles

(d)   rectangles

14. In transition diagrams a state encircled by another represents _________ state.

(a)   Interior

(b)   Start

(c)    Final

(d)   Final or Start

15. DFA stands for _____________________________.
16. _____________ is non empty finite set of symbols.
17. Transition function for NFA is a mapping function given as ___________.
18. The number of states in DFA is _________________ than the number of states in NFA for the same language.
19. We formally denote a finite automation by (Q,∑, δ,q_0,F) where δ is________.
20. _____=∑⁺  U {ε}

Answers:-

1)d,   2) d,   3) b,   4) a,   5) a,   6) a,   7) a,   8) a,   9) b,   10) c,   11) b,   12) b,   13) b, 14) c, 15) Deterministic Finite automata,  16) An alphabet, 17) Q X Σ to 2^Q, 18) More,                      19) Transition Function, 20) Σ^*

UNIT-I-OBJECTIVE QUESTIONS(PART-II)          

1.       Consider a DFA over Σ = {a,b} accepting all strings which have   number of a's divisible by 6 and number of b's divisible by 8. What is  the minimum number of states that the DFA will have ?

(a) 8                       (b) 14                (c) 15                (d) 48

2.       Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.

(a) N2                       (b) 2N                 (c) 2 ^N                      (d) N!

3.       An FSM with output capability can be used to add two given integer in binary representation. This is______________.

(a)   True

(b)   False

(c)    May be true

(d)   None of the above

4.       Choose incorrect statement.

(a)   Moore and Mealy machines are FSM’s with output capability.

(b)   Any given Moore machine has an equivalent Mealy Machine.

(c)    Any given Mealy machine has an equivalent Moore Machine.

(d)   Moore Machine in not a FSM.

5.       The Major Difference between a Moore and Mealy machine is that _____

(a)   The output of former depends on the present state and present input.

(b)   The output of former depends only on the present state.

(c)    The output of former depends only on the present input.

(d)   None of the above.

6.       The number of states of the FSM, required to simulate the behavior of a computer , with a memory capable of storing ‘m’ words, each of length ‘n’ bit is ________________.

(a)   m X 2ⁿ

(b)   2^mn

(c)    2^m+n

(d)   None of the above

7.       The recognizing capabilities of NFA and DFA _____________________.

(a)   May be different

(b)   Must be different

(c)    Must be same

(d)   None

8.       FA has _________________________.

(a)   Unlimited Memory

(b)   No memory at all

(c)    Limited memory

(d)   None

9.       Identify correct statement from the following.

I.             A FSM can be designed to add two integers of any arbitrary length.

II.            Every subset of a countable set is countable.

(a)   I only

(b)   Neither I nor II

(c)    II only

(d)   I and II

10.    Which of the following statement is true?

(a)   The union of two equivalence relation is also an equivalence relation.

(b)   Regularity is preserved under the operation of string reversal.

(c)    All subsets of regular set are regular.

(d)   A minimal DFA that is equivalent to an NFA with n nodes has always 2ⁿ states.

11.    The transition function for DFA is mapping function given as ______________________.

12.    The Minimum number of states required to accept the language L={w|w ε(a+b)^*} is _______.

13.    Finite automation for accepting words “this” and “that” require _________ states.

14.    Elimination of ε edges from NFA increases ________________.

15.    ________ of a state is the set of states that can be reached by ε transitions.

16.    The output in _______ machine is associated with transition.

17.    Two states q₁ and q₂ are __________, if both δ (q₁,x) and δ(q₂,x) are final state, or both of them are non final state for all x Î Σ^*.

18.    If L is accepted by ____________________, then L is accepted by an NFA without Î- transitions.

19.    NFA with ε can increase the processing time of NFA.(True/False)

20.    All Moore Machine have an equivalent Finite Automata. (True/False)

Answers:-

1)      c, 2) c, 3) a, 4) d, 5) b, 6) b, 7) c, 8) c, 9) d, 10) b, 11) Q X Σ to Q, 12) one, 13) seven, 14) number of edges, 15) epsilon closure, 16) mealy, 17) equivalent, 18) NFA with ε- closure,

19) True, 20) False

UNIT-II-OBJECTIVE QUESTIONS (PART-I)    

1. Which of the following regular expression identities are true?

(a)  (r+s)^*=r^*

(b)  (r^*s*)^*=(r+s)^*

(c)   (r+s)^*= r^*+s^*

(d)  r^* s*= r^*+s^*

2.  Which of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as substring?

(a)   0^*(1+0)^*

(b)   0^*1010^*

(c)    0^*1^*01

(d)   0^*(10+1)^*0^*

3. How many string of less than 4 contains the language described by the regular expression (a+b)^*b(a+ab)^*?

(a)   7

(b)   10

(c)    12

(d)   11

4. Consider the regular expression (0+1)(0+1)…….. n time. The minimum state finite automata that recognizes the language represented by this regular expression contains 

(a)   n states

(b)   n+1 states

(c)    n+2 states

(d)   none

5. Suppose A is a finite set with n elements the number of elements in the largest equivalence relation of A is

(a)   n

(b)   n²

(c)    1

(d)   n+1

6. Which of the following statement is false?

(a)   Every finite subset of non-regular set is regular.

(b)   Every subset of a regular set is regular.

(c)    Every finite subset of regular set is regular.

(d)   The intersection of two regular set is regular.

7. Which of following is regular?

(a)   String of 0’s whose length is a perfect square.

(b)   Set of all palindromes made up of 0’s and 1’s.

(c)    Strings of 0’s, whose length is prime number.

(d)   Strings of odd number of zeros.

8. Let ∑={0,1}, L=∑^* and R={0ⁿ1ⁿ such that n>0} then the language L and R are respectively

(a)   Regular, regular

(b)   Not regular, regular

(c)    Regular, not regular

(d)   Not regular, not regular

9. Let R₁ and R₂ be regular sets defined over the alphabet ∑ then

(a)   R₁ ∩ R₂ is not regular

(b)   _­ R₁ U R₂ is not regular

(c)    ∑^*- R₁ is regular

(d)   R₁^* is not regular

10.  The regular expression for the language which contains the words with alphabet of size 4 is ________.
11. If r and s are two regular expression then expression r+s is also ____________.
12. (ε+00)^*+=_____________.
13. Every language defined by finite automation is a ________________ language.
14. The simplified form of regular expression (a(b+a)^*+a)^* is _______________.
15. Language L={a²ⁿ|n>1} is ___________.
16. Language L={w| |w| is prime} is _________.
17. Language L={uv| u Є L, v Є L^R} is _____________.
18. Applying pumping lemma we can show that all languages are not regular. (True/False).
19. Regular expressions are used in representing text patterns in UNIX like operating system. (True/False).
20. Regular sets are not closed under intersection. (True/False).

Answers:-

1)     b,   2) c,   3) d,   4) b,   5) b,   6) a,   7) d,   8) c,   9) c,   10) [a-z]⁴,   11) regular expression, 12) (00)^*, 13) regular,   14) (a+b)^*,    15) regular, 16) not regular, 17) not regular, 18) true, 19) true, 20) false

UNIT-II-OBJECTIVE QUESTIONS(PATR-II)

1. Regular grammar also known as __________ grammar.

(a)   Type 0

(b)   Type 1

(c)    Type 2

(d)   Type 3

2. Which of the following is related to regular grammar?

(a)   Right linear

(b)   Left linear

(c)    Right linear &  left linear

(d)   CFG

3. Regular grammar is a subset of __________ grammar.

(a)   Type 0

(b)   Type 1

(c)    Type 2

(d)   Type 0, 1 & 2

4. P, Q, R are three languages. If P and R are regular and if PQ=R then

(a)   Q has to be regular.

(b)   Q can’t be regular.

(c)    Q need not be regular.

(d)   Q has to be a CFL.

5. A right or left linear grammar is called _________.

(a)   Regular Grammar

(b)   Context sensitive grammar.

(c)    Context free grammar.

(d)   None

6. If all production are of the form AàBw or Aàw, we call it ___________.

(a)   Right linear

(b)   Left linear

(c)    Right linear &  left linear

(d)   None

7. If all production are of the form AàwB or Aàw, we call it ___________.

(a)   Right linear

(b)   Left linear

(c)    Right linear &  left linear

(d)   None

8. Let G=(V,T,P,S) be a CFG. A tree is a derivation tree for G if every vertex has a label which is symbol of ____________________.

(a)   V

(b)   T

(c)    V U T

(d)   V U T U { }

9. Let G=(V,T,P,S) be a CFG. A tree is a derivation tree for G if the label of the root is ___.

(a)   S

(b)   Belongs to V

(c)    Belongs to T

(d)   Belongs to V or T

10. Choose correct statement.

(a)   All languages can be generated by CFG.

(b)   Any regular language has an equivalent CFG.

(c)    Some non regular languages can be generated by CFG.

(d)   Some regular languages can’t be simulated by an FSM.

11. The language constructs which are most useful in describing nested structures such as balanced parentheses matching begins ends etc are _________.

(a)   RE

(b)   CFG

(c)    CSG

(d)   None

12. _________  is denoted by G=(V,T,P,S).
13. A string of terminals and variables α is called a ___________ if S  ^* α.
14. If at each step in a derivation a production is applied to the left most variable, then the derivation is called __________.
15.  If at each step in a derivation a production is applied to the right most variable, then the derivation is called __________.
16. _____________ is a graphical representation of derivation.
17. CFG stands for _____________.
18. Let G=(V,T,P,S) be a CFG. A tree is a derivation tree for G if  vertex is interior and has a label A then A must be in  ____________________.
19. Left linear or Right linear grammar is called __________.
20. If L is a ____________, then L is generated by some left-linear grammar and by some right-linear grammar.

Answers:-

1)      d, 2) c, 3) d, 4) c, 5) a, 6) b, 7) a, 8) d, 9) a, 10) b, 11) b, 12) CFG, 13) sentential form,

      14) left-most,   15) right most,    16) derivation or parse tree, 17) context free grammar,    

      18) V, 19) Regular grammar, 20) regular set