- Computer Science Engineering (CSE)
- Theory of Computation
- Unit 1
- A minimum state deterministic finite aut...

Q. |
## A minimum state deterministic finite automation accepting the language L={W W ε {0,1}*, number of 0s and 1s in are divisible by 3 and 5, respectively} has |

A. | 15 states |

B. | 11 states |

C. | 10 states |

D. | 9 states |

Answer» A. 15 states |

View all MCQs in:
Theory of Computation

- A minimum state deterministic finite automation accepting the language L = {W W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has
- Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below: A B P - Q q R S r R S s R S The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
- Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?
- Which one of the following statement is true for a regular language L over {a} whose minimal finite state automation has two states?
- Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
- In which of the stated below is the following statement true? “For every non-deterministic machine M1, there exists as equivalent deterministic machine M2 recognizing the same language.”
- Consider the regular language L = (111+111111)*. The minimum number of states inany DFA accepting this language is
- Which of the following is true with respect to Kleene’s theorem? 1 A regular language is accepted by a finite automaton. 2 Every language is accepted by a finite automaton or a turingmachine.
- Which of the following statements is/are FALSE? (1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. (2) Turing recognizable languages are closed under union and complementation. (3) Turing decidable languages are closed under intersection and complementation (4) Turing recognizable languages are closed under union and intersection.
- The set that can be recognized by a deterministic finite state automaton is

Login to Continue

It will take less than 2 minutes

Report MCQ