31 questions
0
votes
0
answers
28
views
NuSMV - Issue with counter-based signal activation in Model
I have a project for the Embedded System Design course where I need to model a fault-tolerant sensor reading mechanism. I have reduce the system to only the important parts. The system relies on error ...
0
votes
1
answer
241
views
DFA for input starting with "1", and having "11" in it. Why it doesn't accept this input?
I'm trying to make a Deterministic Finite Automaton (DFA) to accept binary strings that start with "1" and have a substring "11" in it, over {0,1}.
Here is the DFA I created:
...
- 13
0
votes
1
answer
73
views
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 ...
-1
votes
1
answer
221
views
Finite state machine with timer resets
I'll have a real world problem that I try to solve which involves the implementation of a FSM. But I fail to get it right.
My problem: I want to integrate my garage door into my smart home. As it is ...
- 1,773
1
vote
0
answers
29
views
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 ...
0
votes
1
answer
33
views
How does placing the output (word) labels on the initial transitions of the words in an FST lead to effective composition?
I am going through hbka.pdf (WFST paper). https://cs.nyu.edu/~mohri/pub/hbka.pdf
A WFST figure for reference
Here the input label i, the output label o, and weight w of a transition are marked on the ...
0
votes
1
answer
110
views
How to create a deterministic finite automata for the "regular" function where states lead to more than one state depending on the value of an int
the manual of Minizinc says that we can pass an array to the "regular" function that represent the transitions between states of a DFA. For this state machine:
It puts this example:
array[...
- 29
1
vote
1
answer
639
views
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 ...
user19921500
0
votes
1
answer
269
views
Aligning nodes in dot with group does not give the desired result
I tried to create graph from here Improving graphviz layout and want to get the exact picture
like in post, but can't vertically align nodes and get nice curve in q3->q3. My question is about how ...
- 959
0
votes
1
answer
48
views
How do I set a pause between if statements?
I want to write a code that let’s a car drive if low light is detected and stop if a sonar sensor measures less than 20 cm. This has to be repeated. However, if the same low light is detected again ...
-1
votes
1
answer
334
views
Draw an FSA that recognizes: (A∗ | AB+). (The bar outscopes the other operators, so its equal to: (A∗) | (AB+).) Use as few states possible
I've attached what I have. My problem is that I don't know if its correct and if I've even used the fewest states possible to answer this question. Really appreciate any help on what I currently did ...
1
vote
0
answers
62
views
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 ...
- 1,285
1
vote
1
answer
120
views
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 ...
- 11
0
votes
0
answers
29
views
Given a finite character vocabulary, what is the easiest way to represent arbitrarily long sequences of characters with uniform length?
I am attempting to manipulate a finite state transducer for a project. However, in constructing the FST, I need the output symbols to each be some arbitrarily long sequence of characters from the ...
- 15
0
votes
1
answer
1k
views
Is this NFA correctly accepting inputs that end with a 00?
In a lecture it was said that this NFA accepts inputs ending with two zeros or inputs=0: https://ibb.co/9Wt0j7J .
The alphabet is {0,1}
But if the input would be 001 we would on some path also end up ...
- 219
2
votes
1
answer
3k
views
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 ...
1
vote
1
answer
415
views
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 ...
- 109
1
vote
1
answer
408
views
Pumping Lemma for regular language: Can we modify the first condition to 'for each i > 0'?
Pumping lemma from <Introduction_to_the_Theory_of_Computation>"
Question: Can we modify the first condition to for each i > 0 instead of for each i ≥ 0 ?
- 319
0
votes
1
answer
252
views
Is the pumping lemma proof wrong from book <Introduction to the Theory of Computation>?
The proof for 'pumping lemma' from book <Introduction to the Theory of Computation> :
Pumping lemma: If A is a regular language, then there is a number p
(the pumping length) where if s is any ...
- 319
0
votes
1
answer
1k
views
What state will this finite automata go when reading a symbol which is not belong to its alphabet?
As we know, the definition of 'finite state automata' is:
Then we have this finite state automat described as:
Then we have the conclusion:
Question is : Instead of accept an empty string, what if the ...
- 319
1
vote
1
answer
94
views
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.
- 35
0
votes
1
answer
910
views
Why does my screen not update when I click my button the first time, but works perfectly fine afterwards?
This is my first time making a finite state Automata. I tried making a stop light kind of program where if you click the button, the light changes once, starting at green, then to yellow if clicked ...
- 330
0
votes
4
answers
384
views
Game Ai using Enum as Finite State Machine
I want to implement an ai into a simple street fighter style game, and I want to do this with a finite state machine. For a simple example, this FSM has the states:
Attacking, Chasing, Fleeing
From ...
- 593
1
vote
1
answer
436
views
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 ...
- 21
2
votes
1
answer
605
views
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.
...
- 249
1
vote
1
answer
757
views
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 ...
- 1,844
-2
votes
1
answer
414
views
Automaton for prefix matching
Using an open source Java automaton library, eg: org.apache.lucene.util.automaton or dk.brics.automaton, how can I build an automaton for prefix matching?
eg: an automaton created from the set of ...
- 8,877
4
votes
1
answer
4k
views
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 ...
- 710
-1
votes
2
answers
2k
views
How to convert regular expression to finite state machine?
Let the regular expression;
r = (a*|(ab)*)b*
what is the rules for converting this expression to finite state machine?
- 135
0
votes
2
answers
2k
views
npda for the language number a's less than or equal to 3 times the number of b's
I am trying to construct an npda for L = {w ∈ {a,b}*| na(w) <= 3*nb(w)}.
This means that for every b there can be at most 3 a's.
First of all, this is what I have done so far.
From the start ...
- 3
8
votes
2
answers
2k
views
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 ...
- 5,565