Stack Overflow
Stack Overflow

Questions tagged [finite-state-automaton]

Mathematical model of computation used to design computer programs and sequential logic.

Mathematical model of computation used to design computer programs and sequential logic. Simple examples of the finite state machine might be traffic lights or a vending machine.

31 questions
6
votes
2 answers

Are regular expressions (regex) really regular?

I understand how regular expressions got their name, and have read the related question (Why are regular expressions called "regular" expressions?), but am still wondering whether regular expressions are always regular. For example, how can…
Igor Ševo
  • 5,459
  • 3
  • 35
  • 80
4
votes
1 answer

Designing a DFA (alphabet 'a' and 'b') : The number of 'a' in the string must be a multiple of 3, and the string does not contain 'aba'

Here is the problem: And here is my line of reasoning when I first came upon it: This one seems difficult Finding a regular expression for it seems tricky, so i cannot follow this path to convert the regular expression to a DFA So I decided to…
Dang Manh Truong
  • 795
  • 2
  • 10
  • 35
2
votes
1 answer

How to find the language of a NFA

As above, I have a transition graph, but I'm not sure how to find the language of it, seems to me that there are a lot of possibilities, but I must be misunderstanding somehow. My understanding is that any word that leads from the initial to the…
NotTooSmart13
  • 21
  • 2
2
votes
1 answer

PROLOG a particular finite-state-automaton

I can't find an answer for the following problem. The automaton accept strings like "A:5739." or "C::399\4342)", and these reminds me the path of the file system, but i am not sure about that. Problem text: Consider the following finite-state…
Fred_2
  • 249
  • 2
  • 11
1
vote
0 answers

On the use of subsequential symbol $ in Finite state transducers to pad out the context, for composition

I am going through hbka.pdf (WFST paper - https://cs.nyu.edu/~mohri/pub/hbka.pdf) I am trying to understand this paragraph. Pg 22/31. "The deterministic transducer composes without a matching delay, which makes it the better choice in applications.…
Anantha Krishnan
  • 13
  • 3
1
vote
1 answer

How to simplify/generalize a Finite State Machine (FSM) for a vending machine?

I have enrolled into course of computational methods, and currently we are reviewing automata and regular expressions. In one of the course assignments we were asked to design a finite state automata that models the payment process of a vending…
Arturo Olivares
  • 45
  • 4
1
vote
0 answers

Detect cyclic feeding interactions without applying XFST replace rules to lexicon

The following two XFST replace rules represent a cyclic feeding interaction, where the final result includes the original form because the first rule feeds into the second and the second feeds into the first. For example, the first rule would…
reynoldsnlp
  • 1,072
  • 1
  • 18
  • 45
1
vote
1 answer

Generate output based on first character of a word

I am trying to set up a Finite State Transducer with Helsinki Finite State Technology (HFST) for Python. I want if the first character of a word is an 'o' the output is "Positive" and if there are characters following in the same word, output empty…
Evangelos F.
  • 11
  • 1
1
vote
1 answer

how to construct a dfa that recognizes the set of bit string that begins with two D's?

I need help with this solution cause I've just begun studying the finite state automation and couldn't help myself with this problem. does the question mean that I've to give input 1101 1101 & if so how to show the other state to go to if the bit…
Shashank Jha
  • 83
  • 1
  • 10
1
vote
1 answer

Pumping Lemma for regular language: Can we modify the first condition to 'for each i > 0'?

Pumping lemma from " Question: Can we modify the first condition to for each i > 0 instead of for each i ≥ 0 ?
Anonemous
  • 307
  • 2
  • 8
1
vote
1 answer

I cannot figure out if this language is regular, Can it be represented by a nfa?

Is this language regular? I cannot find a solution for it and I have mixed feelings about it, by the way I am only doing these the last 2 weeks.
Naoimi
  • 35
  • 5
1
vote
1 answer

Finite State Automata for a coin change-machine

I'm trying to build a table to describe the behaviour of the FSA for a coin change machine described below. There is a slot that accepts a 50c coin and 2 buttons that a user can press to get a 20c or 10c coin as change. As soon as the 50c coin is…
Kimeru
  • 21
  • 1
  • 3
1
vote
1 answer

Finete State machine visualizer

I need an application that prints/visualizes input/output pairs during the FST runs. I mean, for each state of the fst, it needs to print out a tuple that contains input for that state and output of the state. Right now I can generate fst files that…
zwlayer
  • 1,752
  • 1
  • 18
  • 41
0
votes
1 answer

How to create a singleton in Python that always replaces the previous instance?

I'm working on a game in pygame-ce as a hobby, for scene management I've implemented a finite state machine. The problem is, it currently only kind of works, as the scene object is not garbage collected and then reinitialized in between "state…
Maximilian Hauser
  • 26
  • 4
0
votes
0 answers

Understanding Lexicon FST in yesno example of Kaldi

I am running yesno example in Kaldi. I could get 0 WER at the output, which means things are going right. However, when I tried to view the L.FST, I see some ambiguity. Consider the above L.FST , how to choose the next state from the current state…
Anantha Krishnan
  • 13
  • 3
1
2 3