engineering recuitment GATE CSE 2023-24 Test Series Theory of Computation Regular Languages and Finite Automata Finite Automata
Let the language D be defined on the binary alphabet {0, 1} as follows:
D := {ω ϵ {0, 1}*| substrings 01 and 10 occur an equal number of times in ω}.
For example, 101 ϵ D while 1010 ∉ D. Which of the following must be TRUE of the language D?
[If 01 there in string then 10 also present with the same number of times 01 occur].
1
D is regular
2
D is context-free but not regular
3
D is decidable but not context-free
4
D is decidable but not in NP