# All Questions

8 questions
Filter by
Sorted by
Tagged with
277 views

### An algorithm for comparing a DFA and a regular expression

Assuming I have an encoding of a DFA $<M>$ and a regular expression $<r>$, I'm interested in finding an algorithm for comparing whether or not $L(M)=L(r)$. I have thought about converting ...
15k views

### Steps to convert regular expressions directly to regular grammars and vice versa

I came across following intuitive rules to convert basic/minimal regular expressions directly to regular grammar (RLG for Right Linear Grammars, LLG for Left Linear Grammars): Then I came across many ...
463 views

### Why do we need epsilon-transitions in Thompson's construction?

So as learned every DFA is an NFA. I feel like I understand DFA much better than NFA, so I try to convert my regular expressions to DFA, but I want to understand both sides. For example a|b (a Union ...
1k views

### Brzozowski algebraic method for NFA

Currently I have a graph (basically, a state graph) in Scala which is similar to an NFA some nodes have multiple in/outgoing edges single start state there might be multiple final states a state can ...
2k views

### DFA to regular expression how to deal with 'sink state'

Didn't find a clear statement on this so I just want to make sure I'm right. If I have DFA with edges leading to a 'sink state' (non-accepting state we don't get out of) the edges leading to the sink ...
2k views

### Thompson's Construction Algorithm produces a different NFA

My teacher asked me to convert the regular expression $(a | b)^*$ to an NFA using Thompson's algorithm – well, I'm well aware of how this algorithm works, but since I'm not good at memorising details, ...
In this old exam-task I don't understand all the steps to convert the DFA below to a Regular Expression. The $q_2$ state is eliminated first. The provided solution to eliminate $q_2$ is: If we first ...