GATE CSE 1996 | Finite Automata and Regular Language Question 95 | Theory of Computation

Theory of Computation

Finite Automata and Regular Language

Marks 1 Marks 2 Marks 5

Push Down Automata and Context Free Language

Marks 1 Marks 2

Undecidability

Marks 1 Marks 2

Recursively Enumerable Language and Turing Machine

Marks 1 Marks 2

GATE CSE 1996

MCQ (Single Correct Answer)

-0.3

Let $$L \subseteq \sum {^{^ * }\,} $$ where $$\,\sum { = \,\,\left\{ {a,b} \right\}\,\,} $$ which of the following is true?

$$L = \,\,\,\left\{ {\left. x \right|\,\,\,x} \right.$$ has an equal number of $$a's$$ and $$\,\left. {b's} \right\}$$ is regular

$$L = \left\{ {{a^n}{b^n}\left| {n \ge 1} \right.} \right\}$$ is regular

$$L = \,\,\,\left\{ {\left. x \right|\,\,\,x} \right.\,$$ has more $$a's$$ than $$\left. {b's} \right\}$$ is regular

$$L = \left\{ {{a^m}{b^n}\left| {m \ge 1,\,n \ge 1} \right.} \right\}$$ is regular

GATE CSE 1996

MCQ (Single Correct Answer)

-0.3

Which two of the following four regular expressions are equivalent?
(i) $${\left( {00} \right)^ * }\left( {\varepsilon + 0} \right)$$
(ii) $${\left( {00} \right)^ * }$$
(iii) $${0^ * }$$
(iv) $$0\,\,{\left( {00} \right)^ * }$$

(i) and (ii)

(ii) and (iii)

(i) and (iii)

(iii) and (vi)

GATE CSE 1994

True or False

-0

State True or False with one line explanation:

A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits).

TRUE

FALSE

GATE CSE Subjects

Theory of Computation

Operating Systems

Algorithms

Digital Logic

Database Management System

Data Structures

Computer Networks

Software Engineering

Compiler Design

Web Technologies

General Aptitude

Discrete Mathematics

Programming Languages

Computer Organization