An automaton is a mathematical object describing an abstract machine with a finite set of states and transitions between these that runs on sequences of inputs consisting of letters (or symbols) picked from an alphabet.
Questions tagged [automaton]
130 questions
19
votes
2 answers
Finite automaton in Haskell
What is a good way to represent finite automaton in Haskell? How would the data type of it look like?
In our college, automata were defined as a 5-tuple
(Q, X, delta, q_0, F)
where Q is the set of automaton's states, X is the alphabet (is this…
mathemage
- 356
- 3
- 11
12
votes
4 answers
Scalability of aho corasick
I want to search a text document for occurrences of keyphrases from a database of keyphrases (extracted from wikipedia article titles). (ie. given a document i want to find whether any of the phrases have a corresponding wikipedia article) I found…
z33m
- 5,993
- 1
- 31
- 42
11
votes
3 answers
Combining multiple regular expressions into one automaton
Let's say that I have a list of regular expressions (read from an external source - file, database etc). I want to check which of these regular expressions a string matches.
I can create iterate through all these regular expression and match them,…
Adrian Ber
- 20,474
- 12
- 67
- 117
10
votes
3 answers
Equivalence between two automata
Which is the best or easiest method for determining equivalence between two automata?
I.e., if given two finite automata A and B, how can I determine whether both recognize the same language?
They are both deterministic or both nondeterministic.
franvergara66
- 10,524
- 20
- 59
- 101
10
votes
1 answer
Implementing a code to simulate a finite automaton nondeterministic in c++
I'm doing an assignment for automata theory, which I have to determine whether a word is accepted or not by a transition function for a deterministic finite automaton
I have this input file:
6 8 0 2
2
5
0 0 a
0 1 a
1 1 b
1 2 c
1 3 c
3 4 d
4 4 d
4 5…
novaKid
- 233
- 2
- 4
- 11
7
votes
1 answer
Are there monads that can be used like an automaton?
I'm writing a stream transformer from some Input data type to an Output data type. Input is made by the user, so there is some time between the events. Because each input requires some resource loading, I'd like to "look into the future", i.e. send…
Duschvorhang
- 361
- 1
- 8
7
votes
1 answer
Datalog computational class?
Datalog is not Turing complete.
But what is its computational class?
Is it equivalent to Finite state machine or Pushdown machine (i.e. context free) ... or is it something in between?
Mustafa
- 931
- 1
- 13
- 26
7
votes
2 answers
Implementing A Nondeterminisic Finite Automaton(NFA)
I'm trying to a develop a simulation that executes a non deterministic finite automaton in Java. The first command line argument is a text file that defines the machine. The second argument is an input string. If it accepts the string, it prints to…
donth77
- 605
- 1
- 12
- 23
7
votes
3 answers
Design a nondeterministic finite automata in c++ (incorrect output)
I am doing an assignment for simulate a nondeterministic finite automaton, just as I explain in this post. I have this input read from the file tarea4.in:
1
6 8 0 2
2
5
0 0 a
0 1 a
1 1 b
1 2 c
1 3 c
3 4 d
4 4 d
4 5…
novaKid
- 233
- 2
- 4
- 11
6
votes
3 answers
Pause a thread until a method and all the threads inside finish their work?
I'm new to threads and I was wondering how to use them to make an evaluation in a non deterministic finite automaton.
I have the method that calls another method:
public bool Evaluate2(string s)
{
accepted = false;
ThreadEval(s,…
nightshade
- 638
- 5
- 15
4
votes
3 answers
DFA Minimization Brzozowski algorithm
I am trying to implement Brzozowski's algorithm for minimizing my DFA
Following is the algorithm for the same.
DFA = d(r(d(r(NFA))))
where r() is reversal of NFA and D() converts NFA to DFA.
But I do not understand what is the meaning of r()…
Avinash
- 12,851
- 32
- 116
- 186
4
votes
2 answers
How many languages does a DFA recognize?
According to Sipser's "Introduction to the Theory of Computation": If A is the set of all strings that machine M accepts, we say that A is the
language of machine M and write L(M) = A. We say that M recognizes A ... A machine may accept several…
Paolo Mazza
- 73
- 1
- 6
4
votes
1 answer
What is the intersection of two languages?
Given the languages
L1={anb2m|n,m≥1}
L2={anb3n|n≥0}
L = L1 ∩ L2
I know that L1 is regular language and L2 can be represented by a PDA.
But I don't understand the answer which states that L is {a2nb6n|n≥1}. How was this solution computed?
totoro
- 109
- 2
- 9
4
votes
1 answer
Can you skip epsilon transitions in union expression (Thompson's construction algorithm)
In the picture below can I use both NFA interchangeably? If not then why?
Dennis Grinch
- 353
- 3
- 13
4
votes
0 answers
working with multiple interfaces in scapy
I am trying to make a script to test behavior of network switches and routers. The idea is to run a scapy-based script on a host with multiple network adapters connected to different router ports. The script will send probe packets on one port and…
abb
- 141
- 3