# GATE 1989 Question - Marks 2

Total 7 Questions

GateQuestions

ALL GATE QUESTIONS SUBJECTWISE

×
## Regular Language and Finite Automata

1 Mark Questions
2 Marks Questions
5 Marks Questions

## Context Free Language and Pushdown Automata

1 Mark Questions
2 Marks Questions
5 Marks Questions

## Contextsensitive Language And Turing Machine

1 Mark Questions
2 Marks Questions
5 Marks Questions

## Undecidability

1 Mark Questions
2 Marks Questions

(a) Membership problem in context free languages.

(b) Whether a given context free language is regular.

(c) Whether a finite state automation on all inputs.

(d) Membership problem for Type 0 language.

Total 7 Questions

×
## Correct Option is :

## Explanation

B and D

From the table we can see that it is Undecidable that a CFG is regular or not.

The membership problem of Type(0) language is same as halting problem of turing machine.Which is Undecidable.

×
## Send Error Report:

Divide & Conquer

Greedy Method

Dynamic Programming

P & NP Concepts

GateQuestions.Com is For Serve The Gate Questions For GATE Students at Free Of Cost..
While using this site, you agree to have read and accepted our terms of use,
cookie and privacy policy.
Copyright 2015 - 2018 by GATEQuestions.Com All Rights Reserved.

## Connect with Us: