0
$\begingroup$

$r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$ comes out to be $r_3=r_2=(a+ba)^*bb(a+b)^*$ when i generate the resultant FA and its regex after concatenation i.e. it doesn't include $r_1$
Details:
Consider these two FA
$FA_1$
FA1
$FA_2$
FA2
if $r_1,r_2$ and $r_3$ are regex for $FA_1,FA_2$ and $FA_3$ respectively where
$r_1=(a^*b)^*$
$r_2=(a+ba)^*bb(a+b)^*$
then, mathematically, $r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$
But $r_3$ turns out different when I actually concatenate $FA_1$ and $FA_2$ and use the new transition table (given below) for $FA_3$ to generate its regex ($r_3$) and the $TG_3$ (given below) and then simplify, $r_3$ becomes $(a+ba)^*bb(a+b)^*$ which is the same as $r_2$ (i.e. $r_1$ not prefixed). and since $r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$ can't be simplified into $r_2=(a+ba)^*bb(a+b)^*$
I am convinced that the problem is in the concatenation/transition table, especially with the circular references to $x_1$ and $y_1$, which i don't completely get. That also would mean $TG_3$ iswrong.

The Transition Table:
transition table for fa3

$TG_3$
TG3

Now, it'd be very tedious to explain how i created the transition table, it's easier to figure out by looking at it. but key point i can't quite grasp the "$x_1$ and $y_1$ being connected" part
Sidenotes:
- This is the only way to concatenating two FA that i know of. I am on a distant learning platform and it's quite low quality material, so links to proper methods are appreciated. - If you use another method, please keep in mind that the transition table, regex and the TG and all required - The TG looks like an FA to me (barely know the difference) but the site i used to generate it says it's a TG. what's the difference?

$\endgroup$
2
  • $\begingroup$ I don't see a question. Please, rephrase your post, so that it can be answered. $\endgroup$ Commented Dec 3, 2018 at 15:47
  • $\begingroup$ @AndréSouzaLemos done. added a couple lines at the top and improved the title. $\endgroup$
    – Awaisome
    Commented Dec 4, 2018 at 5:02

1 Answer 1

2
$\begingroup$

You can think of the concatenation of the languages defined by the two automata as the language of the automaton that can be obtained by connecting all final states of the first (in the example, just $x_1$) with the starting state of the second ($y_1$), by an empty transition, and then making them non-final.

A transition table can then be used to convert the NFA just generated into a DFA, which is what you did.

In this case, $r_1r_2$ is indeed equivalent to $r_2$, and this is completely normal. A transition graph represents a transition function, which is part of an automaton. If you minimize $TG_3$, what you get is exactly $FA_2$, which confirms the equivalence.

$\endgroup$
13
  • $\begingroup$ that was very helpful. i have lots of little misc. questions right now we could discuss in chat. but i posted this question like 48 hours ago and now am in a hurry for these three . 1) how is $r_1r_2 = r_2$. i tried to [simplify] (ivanzuzak.info/noam/webapps/regex_simplifier) it. didn't work. 2) what would be the correct Transition table? what i did in my transition table is whenever a resultant state is $x_1$, i append $y_1$ but also vice versa. (which is where i think i went wrong ). 3) how do i minimize $TG_3$. $\endgroup$
    – Awaisome
    Commented Dec 4, 2018 at 13:08
  • $\begingroup$ 1) Your "simplifier" has limits. Try to figure out that everything $r_1$ does can be done without it. 2) after reading a symbol, the transition table should contain only the states where it leads to, plus those connected by empty transitions. 3) there are good resources for that, I see that you used JFLAP. $\endgroup$ Commented Dec 4, 2018 at 13:45
  • $\begingroup$ 1) i am lost here. how do i simplify $r_1r_2$ into $r_2$? 2). i updated the transition table so that when $y_2$ goes to $y_1$ on reading $a$, it doesn't include $x_1$. is it correct now? 3) i am not using JFLAP. i didn't create $FA_1$ and $FA_2$.. i just created the transition table then generated from it $TG_3$ and the $r_3=(a+ba)^*bb(a+b)^*=r_2$. $\endgroup$
    – Awaisome
    Commented Dec 4, 2018 at 14:20
  • $\begingroup$ I'm sorry, this is not a tutoring site. If you have other questions, you can ask them as new posts. Important: try to make them, at least potentially, useful to other people, not just a solution to your problems. $\endgroup$ Commented Dec 4, 2018 at 14:24
  • $\begingroup$ I also strongly encourage you to look for answers to similar questions. $\endgroup$ Commented Dec 4, 2018 at 14:30

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.