I have a set that equals {0,1} I want to find all strings of length 3 or less that have more 0's than 1's.
I can only find threads that are relating to the symbols.
The strings are the following:
0
00
001
010
100
000
A minimal DFA for the language can be found using Myhill-Nerode. We begin considering strings and say whether each one is distinguishable from previous ones.
e: can be followed by L, distinguishable
0: can be followed by e,0,01,10,00,00; distinguishable
1: can only be followed by 00; distinguishable
00: can be followed by e, 0 or 1; distinguishable
01: can be followed by 0 only; distinguishable
10: can be followed by 0 only; indistinguishable from 01
11: can never lead to a string in the language; distinguishable
000: can be followed by e only; distinguishable
001: can be followed by e only; same as 000
010: can be followed by e only; same as 000, 001
100: can be followed by e only; same as 000, 001, 010
???: all other strings of length 3 never lead to a string in L, like 11
????: strings of length over 3 never lead to a string in L, like 11
This gives us the following minimal DFA:
.
|
v
(e)--0-->(0)---0-->(00)
| | |
1 1 0,1
| | |
v v V
(1)--0-->(01)--0-->(000)
| | |
1 1 0,1
| | |
v v v
(11)<--\--/----------/
| ^
| |
\-0,1-/