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.

  • $\begingroup$ Does it say that A and B are regular? If so, you know there are DFAs for each. $\endgroup$ – f9c69e9781fa194211448473495534 Oct 17 '19 at 11:21
  • 1
    $\begingroup$ 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$). $\endgroup$ – Yuval Filmus Oct 17 '19 at 12:20
  • $\begingroup$ I am not sure if A and B are necessarily regular $\endgroup$ – DoubleRainbowZ Oct 17 '19 at 13:00
  • $\begingroup$ @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? $\endgroup$ – DoubleRainbowZ Oct 17 '19 at 13:02
  • 1
    $\begingroup$ Hint: The states of the DFA are the prefixes of strings in $A\setminus B$, together with a failure state. $\endgroup$ – 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$.
| cite | improve this answer | |
  • $\begingroup$ On a tangential note, is $A$ \ $B$ standard terminology for strings in A, but not in B? Is this operator called difference? $\endgroup$ – Gokul Oct 17 '19 at 15:32
  • $\begingroup$ 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. $\endgroup$ – Steven Oct 17 '19 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.