Prove that $A/B$ is regular when $A$ is regular and $B$ is regular or not regular. $$A/B=\{w: wx\in A\ \text { for some }\ x\in B\}$$
Please give me a clue.
Asked
Active
Viewed 790 times
1 Answers
1
Hint. Observe that $$ A/B = \bigcup_{x \in B} A/x $$ and now use the fact that $A$ is regular.
J.-E. Pin
- 40,163
-
$A/B = \bigcup_{x \in B} A/x$ - ok, I agree with you, but I can't finish it. I see that we should ues automata for language $A$. Simply, many of states will be accepted (these states that has a path "at" word $x$ - last state is accepting) – user220688 Mar 11 '15 at 18:14
-
Do you know Myhill-Nerode's theorem? – J.-E. Pin Mar 12 '15 at 07:16
-
No, I don't know – user220688 Mar 12 '15 at 15:04
-
@user220688 Then look at Wikipedia... This is the key to your exercise. – J.-E. Pin Mar 12 '15 at 16:55
-
What about solution without this theorem ? – user220688 Mar 12 '15 at 18:36
-
How does this work when B is infinite? – It'sNotALie. Dec 11 '19 at 14:44
-
@itsnotalie Same answer: look at Myhill-Nerode theorem. – J.-E. Pin Dec 11 '19 at 18:05