No It is not regular. with number of occurrences of '011' we cannot generate number of occurrences of '111'

011011011011011011

A good Question https://gateoverflow.in/1995/gate2014-2-36

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

L={w|the number of occurences of '011' in w is equal to the number of occurences of '111'in w}

Is the above language regular?

Is the above language regular?

0

No It is not regular. with number of occurrences of '011' we cannot generate number of occurrences of '111'

011011011011011011

A good Question https://gateoverflow.in/1995/gate2014-2-36

0 votes

The problem involves comparisons between the number of occurrences of the two strings. Whenever such kind of problem occurs one should look whether we need extra storage or not for comparing.If extra storage(Stack) is required then the language is definitely not regular.

In this problem,

- first we have to count the occurrence of the string '011' and save the count
- after that we can count the occurrence of string '111'.
- compare both the counts.

It requires a storage to save the count of string '011' for comparing later with '111' , hence it is not a regular language.

**Another approach :**

If a Finite Automata could be created for a given language then the language is said to be Regular.

We cannot create a finite automata for the given language hence the language is not regular.

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 450
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,106 questions

45,610 answers

132,247 comments

49,238 users