Build a Regular Expression and Finite Automata

Question

I need some help understanding how take the following to make a regular expression that will be used to generate an epsilon NFA.

Alphabet is {0,1}

Language is: The set of all strings beginning with 101 and ending with 01010.

Valid strings would be:

• 101010
• 10101010
• 101110101
• 1011101010

I am more concerned with understanding how to make the regular expression.

Answer 1

The regular expression you need is pretty simple:

101010|101(0|1)*01010 (theoretical)

or

^101010|101[01]*01010$ (used in most programming languages)

which means either:

• Match 1, 0, 1, 0, 1, 0

or

• Match 1, 0, and 1.
• Keep matching 0 or 1, zero or more times.
• Match 0, 1, 0, 1, 0.

The following non-deterministic automata should work:

Answer 2

To get an idea of what you are looking for, it is helpful to use the intersection operator (denoted & below). It does not belong to the core set of rational expressions, yet it preserves rationality --- in other words, you can use it, and always find a means to express the same language without it.

Using Vcsn, I get this in text mode:

In [1]: import vcsn

In [2]: vcsn.B.expression('(101[01]*)&([01]*01010)').derived_term().expression()
Out[2]: 101010+101(0+1)*01010

and this in graphical mode, showing the intermediate automaton computed using derived_term (which includes details about the "meaning" of each state, so strip called afterwards to get something simpler to read):

Answer 3

I'd suggest a pattern that includes both the base-case and general case. You need to cover the base case of 101010, where the two patterns overlap (starts with "101", ends with "01010", and the last two digits of the first pattern are the first two digits of the second pattern. Then you can cover the general case of "101", any 0s or 1s, "01010", as given by Oscar.

So the full pattern would be:

^(101010|(101[01]*01010))$