1

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.

3 Answers 3

5

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:

enter image description here

7
  • The language isn't specified in the question but are you sure about the (0+1)* part? Why not [01]*?
    – beroe
    Commented Mar 13, 2014 at 0:33
  • @beroe I meant |, and I was using the syntax I learned in a compiler course a long time ago, which I believe is the formal definition, where + or | means an union. Of course, in most programming languages that would be expressed as [01]*, as you pointed out. Check en.wikipedia.org/wiki/Regular_expression#Formal_language_theory Commented Mar 13, 2014 at 1:25
  • 1
    Looks good now. You might also want to anchor it with ^ and $ at the beginning and end, since the current query would match 54321010101012345
    – beroe
    Commented Mar 13, 2014 at 1:32
  • @beroe again, I'm referring to theoretical regular expressions, where that's not required, because when you create the automata, you specify an initial state q_0 and a set of final states (in this example, only one state: <q_8>). I assumed the OP was talking about theoretical regular expressions when he mentioned the alphabet, language, automata, etc. Commented Mar 13, 2014 at 2:45
  • Hi. The theoretical stuff is over my head; I just operate in a practical world, but the unconstrained search term can also match incorrectly with only states 0,1 if it started with 111111...
    – beroe
    Commented Mar 13, 2014 at 4:07
1

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):

Graphical rendering of the automaton

0

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))$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.