The Gateway to Computer Science Excellence

0 votes

Consider the following language:

L = {w| w $\epsilon$ {0,1}* ; w has equal number of occurances of ‘001’ and ‘010’ }

**The solution they provided:** The absolute difference between the number of occurrences of ‘001’ and ‘010’ is at most 1. Hence a DFA can be found.

I did not get the solution. How is it possible? How do we maintain the count of the occurrences of any of these strings?

**One approach I did think:** To move forward if we get ‘001’ and move backward if we encounter ‘010’. But still, this approach will work only if I know in advance that “after a maxm of X occurrences of ‘001’, I am definitely going to find an occurrence of ‘010’ (and vice-versa)). But, **since such info is not given, so how this can be a regular language?**

closed as a duplicate of:
made easy test series

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,272 answers

198,147 comments

104,792 users