Proving a Certain Language Regular

Question

In my computational theory class we have an assignment of proving a language is regular. The language is defined as:

B = {1ky | y is in {0, 1}* and y contains at least k 1s, for k >= 1}

This language looks to me like it would need a pushdown automata to create a machine for this but if someone could push me in the right direction to try and prove this is a regular language. Showing me one of these ways to prove it: creating a NFA, DFA, regular expression, or regular grammar would be helpful.

Auberta

'This language looks to me like it would need a pushdown automata to create a machine' Yes, actually you think this language is something like a^n b^n for n >= 0 which is CFL. But understand this language is something like a^n a^n, for n >= 0 which is a regular language (even number of a )! – Flatware

Answer 1

The language L:

L = {1ky | y is in {0, 1}* and y contains at least k number of 1, for k >= 1}

is a regular language. Indeed this language is very simple. Simple English description for L is: "Set of all strings consists of '0's and '1's with the restriction that: every string starts with '1' and also contains at-least two '1'".

The language description given in question is purposefully complected to make question tricky. Simple approach to solve this kind of problem is: read language try to understand pattern of strings in language. Try to write all possible smallest strings, then write second smallest strings and so on...
Also, try to find smallest length strings those doesn't belongs to the language. Below I have shown my approach with your example to write RE or FA from English description.

Let in first few steps we try to understand what kind of strings are allowed in language L. read following points:

1. All strings in language L are consists of '0' and '1'
2. According to 1ky and k >= 1, all strings in language L must start with '1' as k is grater than 0.
3. Pattern of language strings is 11...y (or we can say 1+y). To explain further, string start with some ones 1s, and has suffix y, where y can be any arbitrary sub string of zeros 0s and ones 1s.
   Note: Because k can be any number greater than 0, there is just a simple constraint that before sub-string y there must be at least one '1'. After first '1' you can consider remain suffix as a part of sub-string y.
4. In other words, we can also explain language L = { 1y, where y contains at least a 1}

Now, as I said try to write some example strings in language:

1. Some smallest possible strings can be:

   '11'   where k = 1 and y = '1' 
   '101'  where k = 1 and y = '01'  
   '110'  where k = 1 and y = '10'
   

2. One more examples:

   '111'  where k = 1 and y = 11 #remember in `y` there must be atleat k ones
   

3. One more examples '1111', Now what can be k and y? string '1111' can be interpreted in following ways:

   '1111'  with k = 1 and y = 111 #remember in `y` there must be atleat k ones
           or   k = 2 and y = 11  #remember in `y` there must be atleat k ones
   

Some example strings those are not in language:

1. String that can't be in L are '0', '00', '01111' because string has to be start with '1'. So all string with pattern 0(0 + 1)* starts with '0' are not in language.

2. There are other possible strings those starts with '1' but still not in language. e.g. '10' because if k = 1 (min value of k) then y is '0'. For same reason, string = '1' not in language. So all strings with pattern 10* that is '1' followed by any number of zeros '0's not in language.

So all string in language starts with '1' and y part also contain at least a '1'. There is no restriction on y that where '1' can be appear. Substring y can be any string of zeros and ones with at-least single one and regular expression for y is: 0*1(1 + 0)*.

Regular expression for L will be: 10*1(1 + 0)*

Now, similar approach can be helpful for writing DFA for language one can refer answer @drawing minmal DFA for the given regular expression and to write regular grammar read answer @Left-Linear and Right-Linear Grammars.

Flatware