210 views
0 votes
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?

1 Answer

0 votes
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,

  1. First we have to count the occurrence of the string '011'  and save the count 
  2. After that we can count the occurrence of  string '111'.
  3. 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.

Since we cannot create a finite automata for the given language

$\Rightarrow$ The language is not regular.

edited by

Related questions

0 votes
0 votes
1 answer
3
practicalmetal asked Mar 25, 2023
374 views
The solution to $X = r +Xs$ by Arden’s Lemma when s has ϵa) an infinite number of solutionsb) a finite number of solutionsc) is always uniqued) none
0 votes
0 votes
3 answers
4
HenryAsks21 asked Mar 4, 2022
1,420 views
For the following question if True show why, and if it’s False show why.)Question: For any language A1, A2, if $A1 \cup A2$ is regular, then A1 and A2 are regular langu...