1
$\begingroup$

I have this problem, and I don't really understand how am I supposed to do this. Could someone please help me with this? I know what left quotient is. I also know about regular, irregular languages. But still I don't know how to show this... Any help would be appreciated, thanks in advance! Also sorry if something is not correctly in English, not my first language.

Problem:

Show that for any language $L ⊆ Σ^*$ and any DFA $A = \langle \Sigma, Q, q_0, \delta, F \rangle$, the left quotient $L \diagdown L (A)$ is a union of languages $L_q = \{v | \delta(q,v) \in F\}$ for selected states $q \in Q$, and explain what are those selected states.

Could someone please also demonstrate on a small (but non-trivial) example, in which the $L$ would be irregular?

$\endgroup$
  • 1
    $\begingroup$ I can't understand the sentence that follows "Problem:". Can you rephrase, and break it down into smaller sentences? Also, what did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. See also meta.cs.stackexchange.com/q/1284/755. $\endgroup$ – D.W. Dec 12 '16 at 3:38
  • $\begingroup$ I'm confused. The left quotient of a language relative to some string $x$ is the set $\{y\mid xy\in L\}$. The thing you're asking about is simply the difference between $L$ and $L(A)$. And the statement you've highlighted can't possibly be true, since any of the langauges $L_q$ is regular and a finite union of regular languages is regular, but the difference of a non-regular language and a regular one might be non-regular (e.g., $L\setminus\emptyset$ for any non-regular $L$.) $\endgroup$ – David Richerby Dec 12 '16 at 9:42
  • $\begingroup$ @DavidRicherby The notation $L \setminus L(A)$ here stands for the left quotient. It is an issue of spacing. $\endgroup$ – Yuval Filmus Dec 12 '16 at 10:18
  • 1
    $\begingroup$ @YuvalFilmus *Mind blown*. It's an issue of being the dumbest notation ever devised. "Oh, no, it's not the backslash that means set difference, it's the slightly different backslash that's also written between two sets and, that looks like weird typesetting and is indistinguishable in handwriting, but which actually means something completely different." $\endgroup$ – David Richerby Dec 12 '16 at 10:38
  • $\begingroup$ @DavidRicherby Probably in this context set difference is denoted by $K-L$. I do not think only spacing will distinguish notions like this. And indeed, in some papers one has to backtrack to the first chapters to check notation that was assumed to be trivial. $\endgroup$ – Hendrik Jan Dec 12 '16 at 22:25
1
$\begingroup$

By definition, $$ L \diagdown L(A) = \bigcup_{x \in L} \{ w : \delta(q_0,xw) \in F \}. $$ The idea now is to use the identity $$ \delta(q_0,xw) = \delta(\delta(q_0,x),w). $$ You take it from here.

$\endgroup$
  • $\begingroup$ The asker has commented (as a new question due to issues with an unregistered account), "But I still can't see why from the answer? Could you please show me some simple example? I cannot figure this out from this answer. Thanks." $\endgroup$ – David Richerby Dec 13 '16 at 17:15
  • $\begingroup$ The only way to learn the subject is to solve exercises. I suggest the OP spend more time with this exercise. $\endgroup$ – Yuval Filmus Dec 13 '16 at 18:19

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.