Theory of Computation
Finite Automata and Regular Language
Marks 1Marks 2Marks 5
Push Down Automata and Context Free Language
Marks 1Marks 2
Undecidability
Marks 1Marks 2
Recursively Enumerable Language and Turing Machine
Marks 1Marks 2
1
GATE CSE 2024 Set 1
MCQ (More than One Correct Answer)
+2
-0

Consider the 5-state DFA $M$ accepting the language $L(M) \subseteq (0+1)^*$ shown below. For any string $w \in (0+1)^*$ let $n_0(w)$ be the number of 0's in $w$ and $n_1(w)$ be the number of 1's in $w$.

GATE CSE 2024 Set 1 Theory of Computation - Finite Automata and Regular Language Question 12 English

Which of the following statements is/are FALSE?

A

States 2 and 4 are distinguishable in $M$

B

States 3 and 4 are distinguishable in $M$

C

States 2 and 5 are distinguishable in $M$

D

Any string $w$ with $n_0(w) = n_1(w)$ is in $L(M)$

2
GATE CSE 2024 Set 1
Numerical
+2
-0

Consider the following two regular expressions over the alphabet {0,1} :

$$r = 0^* + 1^*$$

$$s = 01^* + 10^*$$

The total number of strings of length less than or equal to 5, which are neither in r nor in s, is ________

Your input ____
3
GATE CSE 2023
Numerical
+2
-0

Consider the language L over the alphabet {0, 1}, given below:

$$L = \{ w \in {\{ 0,1\} ^ * }|w$$ does not contain three or more consecutive $$1's\} $$.

The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is ___________.

Your input ____
4
GATE CSE 2021 Set 2
MCQ (More than One Correct Answer)
+2
-0
Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string âˆˆ divisible by three.
A
(0 + 1(01*0)*1)*
B
(0*(1(01*0)*1)*)*
C
(0 + 11 + 10(1 + 00)*01)*
D
( 0+ 11 + 11(1 + 00)*00)*
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