Finding a formula for a specified language

[miltonbradley]

Ok, I've been staring at this problem for hours, but can't figure it out. It concerns finding a formula describing a language.

The language is defined over the alphabet {0, 1} with an equal number of 0s and 1s, and any prefix of a string in the language has at least as many 0's as 1s.

Example of prefixes for swimming:
s
sw
swim
swimm
swimmi
swimmin
swimming

Some strings in the language:
01
0011
0101
010011
010101
001101
001011
000111

This problem is similar to another problem which is much easier to solve:

The language is defined over the alphabet {0, 1} with an equal number of 0s and 1s, and all 0's are before all 1s.

so the formula would be x = 0^M 1^M
where 0^3 1^3 = 000111

Any tips or help would be appreciated. Thanks.

 

[JakeD]

Ok, I've been staring at this problem for hours, but can't figure it out. It concerns finding a formula describing a language.

The language is defined over the alphabet {0, 1} with an equal number of 0s and 1s, and any prefix of a string in the language has at least as many 0's as 1s.

Example of prefixes for swimming:
s
sw
swim
swimm
swimmi
swimmin
swimming

Some strings in the language:
01
0011
0101
010011
010101
001101
001011
000111

This problem is similar to another problem which is much easier to solve:

The language is defined over the alphabet {0, 1} with an equal number of 0s and 1s, and all 0's are before all 1s.

so the formula would be x = 0^M 1^M
where 0^3 1^3 = 000111

Any tips or help would be appreciated. Thanks.

What are the possible operators used in the formula? You've shown one: ^. There must be more, for example, ().

Regular expressions are often used to describe a set of strings. There's more than one operator in regular expressions.

 

[daon]

Ok, I've been staring at this problem for hours, but can't figure it out. It concerns finding a formula describing a language.

The language is defined over the alphabet {0, 1} with an equal number of 0s and 1s, and any prefix of a string in the language has at least as many 0's as 1s.

Example of prefixes for swimming:
s
sw
swim
swimm
swimmi
swimmin
swimming

Some strings in the language:
01
0011
0101
010011
010101
001101
001011
000111

This problem is similar to another problem which is much easier to solve:

The language is defined over the alphabet {0, 1} with an equal number of 0s and 1s, and all 0's are before all 1s.

so the formula would be x = 0^M 1^M
where 0^3 1^3 = 000111

Any tips or help would be appreciated. Thanks.

Are you taking Automata? Fun class..

Anyway, the (0^M)(1^M) is not a regular language. Instead, write 0*1*, which IS a regular language. The expression (0^M)(1^M) is only defined as a language when you bound M. For example, (a^M)(b^M) where M <= 3 is a language. Just for future reference.

In your case, a condition stipulates that given any prefix of an accepted string (with an equal number of 0s and 1s), the number of zeros must be greater than or equal to the number of 1s that have appeared thus far.

Some examples of strings that should be accepted:

01001101
00001111
00101011
01
001011
010101
etc

Strings that should not be accepted (notice, however that the first condition still holds):

0110
0111000
01010110
1001
0000111110

etc
-------


Here is how I would attempt it:
I would first create an NFA accepting this string input. Then create a "fuax" start state and a "faux" accept state and, one by one, remove a node making sure to preserve the lanuage. If you haven't been taught that, then here's a hint:

\(\displaystyle \epsilon\) U (0⁺(0 U 1)*1⁺)

This has no way of keeping track of the number of zeros and ones, but it allows for the iterations to vary as the machine pleases. NOTE that accepted strings will ALWAYS end in a 1 (or else be epsilon).

Informally (since expressions with unbounded varibles do not define languages), (0^M)(0^X U 1^Y)*(1^N) with the following restrictions (aside from epsilon): M>=N>=1, X>=Y, M>=Y-1 (since N>=1), M+X = N+Y.

Hope that helps,
-Daon