Stack Overflow
Stack Overflow

Questions tagged [finite-automata]

A finite automaton (FA) is a mathematical description of an algorithm capable of parsing regular languages. FAs have no external memory, and as such can only take into account a fixed number of previous symbols when processing strings. A deterministic FA (DFAs) is one for which there is only ever one legal transition between states; nondeterministic FAs can be transformed into equivalent DFAs. FAs are the weakest of the commonly-defined automata.

585 questions
242
votes
11 answers

Can regular expressions be used to match nested patterns?

Is it possible to write a regular expression that matches a nested pattern that occurs an unknown number of times? For example, can a regular expression match an opening and closing brace when there are an unknown number of open/close braces nested…
Richard Dorman
  • 23,170
  • 16
  • 45
  • 49
134
votes
20 answers

Is there a typical state machine implementation pattern?

We need to implement a simple state machine in C. Is a standard switch statement the best way to go? We have a current state (state) and a trigger for the transition. switch(state) { case STATE_1: state = DoState1(transition); break; …
Benoit
  • 37,894
  • 24
  • 81
  • 116
66
votes
11 answers

How useful is Turing completeness? are neural nets turing complete?

While reading some papers about the Turing completeness of recurrent neural nets (for example: Turing computability with neural nets, Hava T. Siegelmann and Eduardo D. Sontag, 1991), I got the feeling that the proof which was given there was not…
Albert
  • 65,406
  • 61
  • 242
  • 386
59
votes
4 answers

What is a finite state transducer?

Can someone please tell me what a finite state transducer is? I have read the Wikipedia article and don't understand a thing.
user581734
  • 1,219
  • 3
  • 15
  • 24
56
votes
8 answers

Practical non-Turing-complete languages?

Nearly all programming languages used are Turing Complete, and while this affords the language to represent any computable algorithm, it also comes with its own set of problems. Seeing as all the algorithms I write are intended to halt, I would like…
Kyle Cronin
  • 77,653
  • 43
  • 148
  • 164
50
votes
5 answers

DFA vs NFA engines: What is the difference in their capabilities and limitations?

I am looking for a non-technical explanation of the difference between DFA vs NFA engines, based on their capabilities and limitations.
blunders
  • 3,619
  • 10
  • 43
  • 65
32
votes
10 answers

State Machines and User Interface work -- any examples/experience?

I'm looking for ways to de-spaghttify my front-end widget code. It's been suggested that a Finite State Machine is the right way to think about what I'm doing. I know a State Machine paradigm can be applied to almost any problem. I'm wondering if…
morgancodes
  • 25,055
  • 38
  • 135
  • 187
31
votes
7 answers

How are finite automata implemented in code?

How does one implement a DFA or an NFA for that matter in Python code? What are some good ways to do it in Python? Are they ever used in real world projects?
user5899005
  • 451
  • 1
  • 4
  • 5
30
votes
2 answers

How to use the intersection construction to form a DFA?

I'm doing a homework assignment for my theory of computation class and am a bit confused how to combine 2 DFAs. The book says it uses the "intersection construction" to do so, but I'm not sure what that is. Here are 2 examples:
jfisk
  • 6,125
  • 20
  • 77
  • 113
29
votes
8 answers

Does C# include finite state machines?

I've recently read about the boost::statechart library (finite state machines) and I loved the concept. Does C# have a similar mechanism ? Or can it be implemented using a specific design pattern?
Maciek
  • 19,435
  • 18
  • 63
  • 87
23
votes
6 answers

Shortest regex for binary number with even number of 0s or odd number of 1s

Write an expression that contains an even number of 0s or an odd number of 1s I got it down to: 1*(01*01*)* + 0*10*(10*10*)* where the first part represents an even number of 0s and the second part an odd number of 1s However, there's supposed to…
user3085290
  • 285
  • 1
  • 2
  • 10
21
votes
9 answers

To use goto or not?

This question may sound cliched, but I am in a situation here. I am trying to implement a finite state automaton to parse a certain string in C. As I started writing the code, I realised the code may be more readable if I used labels to mark the…
Abhinav Upadhyay
  • 2,477
  • 20
  • 32
18
votes
4 answers

How do you normalize a finite state machine?

How do you find the minimal Deterministic FSM? Is there a way to normalize non-deterministic FSMs? Is there a linear time bound algorithm to find the minimal FSM for a given machine? Is there a way to see if two FSMs are equivalent? This is…
unj2
  • 52,135
  • 87
  • 247
  • 375
15
votes
8 answers

What is the use of finite automata?

What is the use of finite automata? And all the concepts that we study in the theory of computation. I've never seen their uses yet.
nicky
  • 3,810
  • 9
  • 35
  • 44
14
votes
4 answers

To make sure: Pumping lemma for infinite regular languages only?

So this is not about the pumping lemma and how it works, it's about a pre-condition. Everywhere in the net you can read, that regular languages must pass the pumping lemma, but noweher anybody talks about finite languages, which actually are a part…
Lars Knickrehm
  • 739
  • 4
  • 14
1
2 3
…
38 39