Eliminate Lambda/epsilon

[lewiuberg]

I have made a method to transform an ε-NFA to an NFA, or eliminating lambda/epsilon if you will.
Since this is a step in the process of transforming an ε-NFA to DFA, I thought it could be nice to include it in this project?

             0   1   λ
→*q0         ∅  q1  q2
q1    {*q0,q2}  q2   ∅
q2           ∅   ∅   ∅

transforms to:

             0   1
→*q0         ∅  q1
q1    {*q0,q2}  q2
q2           ∅   ∅

[caleb531]

@lewiuberg I am open to this idea! Can you please submit a pull request with your method? Please add the relevant tests, as well.

[lewiuberg]

Great! I will write tests and submit a pull request this weekend (busy week).

[caleb531]

Hi, @lewiuberg! I just wanted to check if you've had a chance to work on this. I am looking to release v4.1.0 soon, and would love to include this in here.

[lewiuberg]

Hi!

Just started a new role, so sorry for the delay. I will have a look at it asap :)

[lewiuberg]

I have added the code now on my fork. I will try to write the test tonight after my kids' birthday party, or else I'll do it tomorrow.

[caleb531]

@lewiuberg Oh gosh, no rush! Take the time to be present at your kids' birthday party. I'm not in that much of a rush to push out a new release. Please work at your own pace. :)

[lewiuberg]

Hi Caleb! I'm sorry to say i found a bug in the code, so i have to review the while thing before submitting a pull request. I am a little short on time the next couple of days, but I hope to get it done soon.

[caleb531]

@lewiuberg No worries! Thanks for at least keeping tabs on it; that's all I hope for.

[caleb531]

@lewiuberg BTW, just want to add: when you eventually submit your PR, please set the target branch to v5. That is my pending release branch which I will merge into master when all is said and done.

[interrogator]

Would really love this feature @lewiuberg , any updates?

[interrogator]

@lewiuberg I'm currently using your fork and the lambda branch, which appears to be working. Unfortunately I can't make issues there, so I'll try to reach you here.

First, I'd love if you could get that branch merged in here, it's really helpful.

Second, I wonder if you could add an option to your NFA.eliminate_lambda method.

For example, I generate this NFA with epsilon:

After running eliminate_lambda, I get:

What I would like to generate instead is the equivalent:

Would you consider coding an option for this, or providing me with some tips so that I can adjust your code and do it myself?

Thanks so much!

[lewiuberg]

@interrogator Hi! I completely forgot about this :) When I was supposed to make a pull request last time, I got some errors. However, that could be due to my lacking automata skills (since I hadn't used it since I took the course). If you are confident that my implementation works when testing it on something you have the correct answers for, I can prepare a pull request as soon as I'm able.

As for the modification, I can sure have a look at it. It's high time that I brush up on this topic. I had great plans for the visual-automata wrapper, but got swamped at work and school :)

Sorry for the delay @caleb531 I forgot about this one :)

[interrogator]

Would be wonderful if you took a look at it. Personally I don't think I am in a position to say that your PR could me merged, but your lambda branch works fine for me, so even if you managed to introduce the option I described above in that branch, I would be satisfied. But since others would benefit too, I would encourage you to get it merged here!

[interrogator]

@lewiuberg I don't see the harm in you at least opening the PR here and letting the maintainers of this repo reviewing it and deciding the next steps!

[caleb531]

@interrogator The maintainer of the repo here! 😁 Yep, I would be happy to review any PRs that come my way.

[lewiuberg]

Hi guys! Sorry for the delay. I will deliver my thesis may 25th, and this is the first item on my to-do list. Again, very sorry for the delay!

[caleb531]

Hi, @lewiuberg—I hope you are well! I just wanted to follow up on this, as I am interested in wrapping up Automata v6 soon now that #46 has been merged to my new develop branch.

There were many changes in the aforementioned PR, so if you are still able to implement the functionality in this thread, you can find the latest state of the repository on the develop branch (this is also where you should submit any PRs going forward).

[lewiuberg]

Hi, @caleb531!

I'll look into it right now. I have changed work since we last spoke. So [excuse for excuse in not_good_enough] 😅

[lewiuberg]

@caleb531 I see that there is an eliminate_lambda method there now. However, it does not produce the results I made as a blueprint for myself when I made mine. So I guess you have reached the conclusion that it does not work properly?

So I will submit a PR overwriting this method. To me it looks like some protected method are only used for the eliminate_lambda method. I will list the below, and remove them as well if you agree.

• _compute_reachable_states()
• _remove_unreachable_states()
• _remove_empty_transitions()

[caleb531]

@lewiuberg Ah, that NFA.eliminate_lambda method appears to have been recently added by @abhinavsinha-adrino in 0e0da75.

However, if you feel you can write a better / simpler / more efficient implementation, then I'd say go for it! And that means you can remove any unused helper methods as well, as long as the tests still pass!

[abhinavsinha-adrino]

@caleb531 I see that there is an eliminate_lambda method there now. However, it does not produce the results I made as a blueprint for myself when I made mine. So I guess you have reached the conclusion that it does not work properly?

So I will submit a PR overwriting this method. To me it looks like some protected method are only used for the eliminate_lambda method. I will list the below, and remove them as well if you agree.

• _compute_reachable_states()
• _remove_unreachable_states()
• _remove_empty_transitions()

@lewiuberg Hi, can you specify your test case which does not produce an expected result?

I have implemented it in the way @interrogator asked here #31 (comment)

[lewiuberg]

@caleb531 I have tested @abhinavsinha-adrino's

My test case

Here they look pretty much the same. Except mine keeps q2 as {}

Diagrams are equal.

nfa = NFA(
    states={"q0", "q1", "q2"},
    input_symbols={"0", "1"},
    transitions={
        "q0": {"": {"q2"}, "1": {"q1"}},
        "q1": {"1": {"q2"}, "0": {"q0", "q2"}},
        "q2": {},
    },
    initial_state="q0",
    final_states={"q0"},
)

Original table

             0   1   λ
→*q0         ∅  q1  q2
q1    {*q0,q2}  q2   ∅
q2           ∅   ∅   ∅

@abhinavsinha-adrino's implementation table after elimination

             0   1
→*q0         ∅  q1
q1    {*q0,q2}  q2 

My implementation table after elimination

             0   1
→*q0         ∅  q1
q1    {*q0,q2}  q2
q2           ∅   ∅

@abhinavsinha-adrino's test case

nfa = NFA(
    states={"0", "1", "2", "3", "4", "5", "6"},
    initial_state="0",
    input_symbols={'a', 'b', 'c'},
    transitions={
        "0": {'a': {"1"}},
        "1": {'': {"2", "6"}, 'b': {"2"}},
        "2": {'': {"4"}, 'c': {"3"}},
        "4": {'a': {"5"}},
    },
    final_states={"3", "6"}
)

Original table

    a  b   c       λ
→0  1  ∅   ∅       ∅
1   ∅  2   ∅  {2,*6}
2   ∅  ∅  *3       4
4   5  ∅   ∅       ∅

Diagram:

@abhinavsinha-adrino's implementation table after elimination

     a  b   c
→0  *1  ∅   ∅
*1   5  2  *3
2    5  ∅  *3

Diagram:

My implementation table after elimination

              a      b   c
→*0  {1,2,4,*6}      ∅   ∅
1             5  {2,4}  *3
2             5      ∅  *3
4             5      ∅   ∅

Diagram:

Conclusion

From what I can see they are both "correct". But I am a bit rusty on my automata at this point, so I would like you both to conclude which one is the better :)

[abhinavsinha-adrino]

@lewiuberg i see that in your implementation for my test case, the start state 0 is an accept state, but that should not be. I think it's a small error. It will recognise the same language after this correction.

[lewiuberg]

You are absolutely correct @abhinavsinha-adrino. I knew (as I have mentioned earlier) that something was off with my implementation. Because some of my test cases did not work as expected. It was the reason I didn't submit a PR. I think we should keep your implementation.

@caleb531 As a reference I will include my code:

@property
def _lambda_transition_exists(self) -> bool:
    """
    Checks if the nfa has lambda transitions.
    Returns:
        bool: If the nfa has lambda transitions, returns True; else False.
    """
    status = False
    for transitions in self.transitions.values():
        if "" in transitions:
            return True
    return status

@classmethod
def eliminate_lambda(cls, nfa):
    """
    Eliminates lambda transitions, and returns a new nfa.
    Args:
        nfa : A NFA object.
    Returns:
        nfa_lambda_eliminated: A NFA object without lambda transitions.
    """
    if nfa._lambda_transition_exists:
        nfa_lambda_eliminated = nfa.copy()

        for state in sorted(nfa_lambda_eliminated.transitions):
            # Find lambda closure for the state.
            closures = nfa_lambda_eliminated._get_lambda_closure(state)

            if nfa_lambda_eliminated.initial_state == state:
                if closures.difference(state).issubset(
                    nfa_lambda_eliminated.final_states
                ):
                    [
                        nfa_lambda_eliminated.final_states.add(state)
                        for state in closures.intersection(state)
                    ]

            for input_symbol in nfa_lambda_eliminated.input_symbols:
                next_states = nfa._get_next_current_states(
                    closures, input_symbol
                )

                # Check if a dead state was returned.
                if next_states != set():
                    # Update the transition after lambda move has been eliminated.
                    nfa_lambda_eliminated.transitions[state][
                        input_symbol
                    ] = next_states

            # Delete the lambda transition.
            if "" in nfa_lambda_eliminated.transitions[state]:
                del nfa_lambda_eliminated.transitions[state][""]

        return nfa_lambda_eliminated
    else:
        return nfa

[caleb531]

Closing this ticket now that Automata v6 is released with a dedicated NFA.eliminate_lambda method.

https://pypi.org/project/automata-lib/