# Constructing a DFA of strings that are in A but not in B

I am tasked with creating a DFA for the regular language L = A/B, which are the strings that are in A but not in B. The alphabet is Σ = {a,b,c}

I am not really sure where to even start with this one, so any hints or suggestions would be much appreciated. I have never really encountered anything like this before. How do I represent "not in B". I have only dealt with more 'tangible' things, such as divisible by 5, ab(cb), etc. This doesn't really have a rule...I don't even know what the set B is.

• Does it say that A and B are regular? If so, you know there are DFAs for each. – f9c69e9781fa194211448473495534 Oct 17 '19 at 11:21
• Remove all strings in $B$ (if any) from $A$. Now you have reduced to the problem of constructing a DFA for all strings in some set $C$ (where $C = A \setminus B$). – Yuval Filmus Oct 17 '19 at 12:20
• I am not sure if A and B are necessarily regular – DoubleRainbowZ Oct 17 '19 at 13:00
• @YuvalFilmus But how do i construct a DFA with things I don't know if they exist or not? For example if I know a string is abaaabac I can easily construct a DFA, but here I don't know what is in A or B, I can't just go if taking a goes to state q5 for example, because I don't know whats in the string? – DoubleRainbowZ Oct 17 '19 at 13:02
• Hint: The states of the DFA are the prefixes of strings in $A\setminus B$, together with a failure state. – Yuval Filmus Oct 17 '19 at 13:06

Take a DFA $$D_A$$ for $$A$$ and a DFA $$D_B$$ for $$B$$.
Define a DFA $$D$$ for $$A \setminus B$$ as follows:
• The set of states of $$D$$ is the cartesian product of the set of states of $$D_A$$ with the set of states of $$D_B$$.
• The initial state of $$D$$ is $$(a_0, b_0)$$ where $$a_0$$ is the initial state of $$D_A$$ and $$b_0$$ is the initial state of $$D_B$$.
• A state $$(a,b)$$ of $$D$$ is an accepting state iff $$a$$ is an accepting state of $$D_A$$ and $$b$$ is not an accepting state of $$D_B$$.
• A state $$(a,b)$$ has a transition to state $$(a',b')$$ when character $$c \in \Sigma$$ is read, which I will denote by $$(a,b) \xrightarrow{c} (a', b')$$, if and only if $$a \xrightarrow{c} a'$$ in $$D_A$$ and $$b \xrightarrow{c} b'$$ in $$D_B$$.
• On a tangential note, is $A$ \ $B$ standard terminology for strings in A, but not in B? Is this operator called difference? – Gokul Oct 17 '19 at 15:32
• A language is a set (of words) by definition. The $"\setminus"$ operator is the set difference, i.e., $A \setminus B$ is a set containing all elements in $A$ that are not in $B$. Since the property of "being a language" is hereditary (a subset of a language is also a language), $A \setminus B$ will also be a language. So, yes, this is a standard notation. – Steven Oct 17 '19 at 15:35