Finding the DFA

Question

Create a DFA such that L subscript 4 = {0,1}* - {0,01}* and list the first five strings in lexicographic order.

I'm having trouble deducing what L subscript 4 implies, does it be a language of strings with length 4? Also, when we subtract two languages, could we choose the string "1" subtracted from the empty string, meaning can be choose the first {0,1}* to be of length 1 subtracted from {0,01}* of length 0?

Usually it just means a language with the name "L subscript 4" — Bergi, Apr 06 '14 at 23:47
You cannot subtract strings. Could it mean that you should substract the one language from the other: `L_4 = L({0,1}*) - L({0,01}*)`? — Bergi, Apr 06 '14 at 23:48
You are correct Bergi, I meant the Language {0,1}* but by string i mean that the strign that the language creates. — azureskys, Apr 07 '14 at 00:27
I think your question doesn't make any sense then (any more). Would you mind to rephrase the part about "choosing the string"? Subtracting languages works like set difference: "all strings from L1 that are not in L2" — Bergi, Apr 07 '14 at 00:28
I think my problem is the subtraction of two languages. For instance, do we find all strings of length one in both language and then create a new language , L4 such that each string in L4 contains a string in {0,1}* but not in {0,01}*? And do this iteratively for string of length 2 3 ... So would the first five strings of L4 be 1 10 11 011 101 — azureskys, Apr 07 '14 at 00:45
No, not that "each string in L4 contains a string…" but that "each string in L4 *is* a string…". Your first five strings look fine. However, notice that you're not supposed to create a language, but simply a DFA. And remember what "complement" means — Bergi, Apr 07 '14 at 01:08
What exactly would the DFA be? I made one but I'm not sure how to replicate it on stackoverflow. I dont think it's correct after reading the complement portion.Would it simple be the DFA for the L({0,1}*) and then take the complement of it? — azureskys, Apr 07 '14 at 02:36
Sorry, i mean the DFA for {0,01}*, meaning that there are only two states? — azureskys, Apr 07 '14 at 02:49
@azureskys learn [complement dfa](http://stackoverflow.com/questions/14802732/finding-the-complement-of-a-dfa/14817545#14817545) L = `{0, 1}* - {0, 01}*` means complement of language `{0, 01}*` — Grijesh Chauhan, Apr 07 '14 at 06:58
Yes, it would be simply the complement of the DFA for that language `{0,01}*`, but there are more than two states (don't forget the error state) — Bergi, Apr 07 '14 at 09:07

score 0 · Answer 1 · answered Oct 26 '16 at 21:02

The language {0,01}* is the set of strings that before each 1 there should be one 0. For example 00010001 is in this language but 10000 or 0001111 are not. {0,1}* is on the other hand, is all the strings with alphabet {0,1}. Now subtracting these results a language where at least has one 1 and all the 1's come before any 0. For example 1111000 is in L_4 but 000000 or 011111 are not.

score 0 · Answer 2 · answered Oct 26 '16 at 21:11

The notation {0, 1}* - {0, 01}* is set subtraction - it means "the language of all strings in {0, 1}* that aren't in {0, 01}*." When they write

L₄ = {0, 1}* - {0, 01}*

I believe they're defining a new language called L₄ that's equal to the above expression.

To solve this problem, you might find it useful to notice that L₄ is the complement of the language {0, 01}*. One way to solve this problem would be to build a DFA for {0, 01} * and to then flip all the accepting and rejecting states. That will give you a DFA for L₄.

I'll leave the rest of the problem as an exercise to the reader. :-)

Finding the DFA

2 Answers2