7 votes

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 ...
user avatar
  • 7,155
7 votes

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 ...
user avatar
  • 1,439
4 votes

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 ...
user avatar
  • 143
2 votes

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 ...
user avatar
2 votes
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 ...
user avatar
  • 27.2k
2 votes
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 ...
user avatar
  • 27.2k
2 votes
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 ...
user avatar
2 votes
Accepted

NFA to recognize the language ${ab}$

It is because of the method used for the construction. The NFA that results from the concatenation of the languages of two automata $A_1$ and $A_2$ is the juxtaposition of $A_1$ and $A_2$ with $\...
user avatar
  • 7,155
1 vote

NFA to recognize the language ${ab}$

The procedure described in the text is a systematic method for converting a regular expression to an NFA. It’s a recipe that works, and so you don’t have to think much to prove that the language of ...
user avatar
1 vote

Prove that the language of regular expressions is not regular

Yes, this will work: if you may assume that the language of matching brackets is non-regular, it suffices to know that whenever a language is regular, erasing all occurrences of a particular character ...
user avatar
  • 4,611
1 vote

What exactly is pumping length in pumping lemma?

The "Pumping Length" "n" exists because you can write a finite automata that classifies all strings up to a fixed, finite length in any way it wants to. Your finite automata can ...
user avatar
  • 785
1 vote

What exactly is pumping length in pumping lemma?

When using the pumping lemma, you do assume such $p$ exists, assuming that the language is regular. This $p$, no matter what it is, should exists since it is the number of states for the DFA of the ...
user avatar
  • 1,257
1 vote

Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's

Here is how to construct a regular expression for the set of strings over $\{a,b\}$ which contain an even number of $a$'s and at most one $b$. Strings that contain no $b$ are of the form $a^n$, where $...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible