-1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Does it say that A and B are regular? If so, you know there are DFAs for each. $\endgroup$ Oct 17, 2019 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$ Oct 17, 2019 at 12:20
  • $\begingroup$ I am not sure if A and B are necessarily regular $\endgroup$ Oct 17, 2019 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$ Oct 17, 2019 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$ Oct 17, 2019 at 13:06

1 Answer 1

1
$\begingroup$

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$.
$\endgroup$
2
  • $\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, 2019 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, 2019 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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