Home » Theory of Computation » Theory of computation miscellaneous » Question

Theory of computation miscellaneous

Theory of Computation

  1. Which of the following statements is true?
    1. If a language is context-free it can always be accepted by a deterministic push-down automata
    2. The union of two context-free languages is contextfree
    3. The intersection of two context-free languages is context-free
    4. The complement of a context-free language is context-free
Correct Option: B

Option (a) False : If the language is context-free then it cannot be said that the language will be accepted by the deterministic push-down automaton as there are some cases defined where the context-free language is not accepted.
Option (b) True : The union of context-free languages always produces a context-free language but it not the case with intersection of two context-free languages.
Option (c) False : As discussed in Option (b).
Option (d) False : Similar to intersection, complement of a context-free language is not always a context-free language.



Your comments will be displayed only after manual approval.