Questions taken from Stackoverflow
This page lists questions about automata and other rational/regular expressions that were asked on Stackoverflow, and where Vcsn seems to be an appropriate tool to compute the answer.
Build a Regular Expression and Finite Automata
The set of all strings beginning with 101 and ending with 01010.
First, let's define our "context": we work with "labels are letters" (lal), on the alphabet . We don't use weights, or rather, we use the traditional Boolean weights: .
Then, we build our expression using an unusual operator: denotes the conjunction of expressions and . In this case (unweighted/Boolean automata), it denotes exactly the intersection of languages.
We want to normalize this extended expression (it has conjunction and complement operators) into a basic expression. To this end, we first convert it to an automaton.
and then we convert this automaton into a basic expression:
Or, in ASCII:
Regular expression to match text that doesn't contain a word?
I'd like to know if it's possible to match lines that don't contain a specific word (e.g. hede) using a regular expression?
First, let's define that alphabet we work on: from to for instance.
Then we define our expression, which is extended (it uses the complement operator), so to normalize it, we first convert it into automaton (with _expression_.automaton
), from which we extract a basic expression (with _automaton_.expresion
).
Or, in ASCII (+
is usually denoted |
; \e
denotes the empty word; and [^]
denotes any character, usually written .
):
Convert finite state machine to regular expression
Is there a tool (or an algorithm) to convert a finite state machine into a regular expression?
Vcsn is tool for rational expressions and automata. See http://vcsn.lrde.epita.fr.
Build a random automaton of 4 states, labeled by letters to choose in . Then "lift" it into an automaton labeled by expressions.
Eliminate state 2, then 3, etc. The order does not matter for correction (any order gives a correct result), but the quality of the result does depend on this order.
Eliminate the last state, and read the answer.
Alternatively, you can use the method automaton.expression
to ask for the result.
You may see this algorithm run "interactively" using %demo
.
Constructing a Regular Expression from a Finite Automata
I'm trying to construct a regular expression from a Finite Automaton but found my self completely stuck with this one.
How to find the right quotient of a language given two languages?
(This is the question with typos in and fixed.)
If and . I am not getting how the DFA for is constructed in the second figure using the DFA for , please tell me the approach.
First, let's define our "context": we work with "labels are letters" (lal), on the alphabet . We don't use weights, or rather, we use the traditional Boolean weights: .
Then define the first automaton, Figure 4.1.
Automaton represents the language :
We may now compute the quotient, which is indeed the automaton of Figure 4.2. It is better looking once trimmed.