McqMate

Q. |
## Which of the following statement is true? |

A. | All languages can be generated by CFG |

B. | The number of symbols necessary to simulate a Turing Machine(TM) with m symbols and n states is mn. |

C. | Any regular languages have an equivalent CFG. |

D. | The class of CFG is not closed under union. |

Answer» C. Any regular languages have an equivalent CFG. |

2.4k

1

Do you find this helpful?

6

View all MCQs in

Theory of Computation
MA

2 years ago

Study very good

0

- 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.”
- Which one of the following statement is true for a regular language L over {a} whose minimal finite state automation has two states?
- Consider the following statements I. Recursive languages are closed under complementation II. Recursively enumerable languages are closed under union III. Recursively enumerable languages are closed under complementation Which of the above statement are TRUE?
- Which statement is true?
- Which statement is true?
- Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is
- = ∈{ } w has at least as many occurrences of (110)’s as (011)’s}. Let L {w 0,1 * 2 = ∈{ } w has at least as many occurrence of (000)’s as (111)’s}. Which one of the following is TRUE?
- 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.
- 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 of the following is TRUE?