# Tag Info

### Length of a regular expression

There are two conventions I know of. One is defining the size of a regular expression as the size of the binary tree representing the expression. As such, the size of the expression is the total ...
• 7,155

### Length of a regular expression

I assume, you want to define the length of a regular expression such that you can make statements like: The Thompson construction creates an NFA from a regular expression with a number of states that ...
• 1,439

### Proving Equivalence of Two Regular Expressions

If you wanted to prove this extra formally, you could try to prove this in a proof assistant, such as Lean (or Coq or Agda or ...). Here's how you can state that problem using Lean's ...
• 143

### Proving Equivalence of Two Regular Expressions

If you generate a minimal DFA from a regular expression, then you can label each state uniquely with the lexically smallest string that reaches the state. This makes it very easy to check for ...
Accepted

### Converting Regular Expression to Finite Automata

The construction that you show from the book of Sipser is known as Thompson’s construction, building a nondeterministic automaton with $\varepsilon$-transitions. Those empty transitions can be removed ...
• 27.2k
Accepted

### Converting Deterministic Finite Automata to Regular Expression

Jacques Sakarovitch studies the outcome of the various algorithms. See his paper The Language, the Expression, and the (Small) Automaton (CIAA 2005. LNCS 3845), where some results are summarized that ...
• 27.2k
Accepted

### What exactly is pumping length in pumping lemma?

The pumping length $n$ must be assumed to be arbitrary - you can't fix it to be a particular value. The pumping lemma is used to prove that a given language is nonregular, and it is a proof by ...
• 1,005