Most voted "automata" questions
An automaton is set to run over a given sequence of inputs in discrete time steps. For each step, an automaton receives an input that is obtained from a set of symbols or letters, which is called the alphabet. At any time, the symbols that serve as input for the automaton form a finite sequence of symbols, which is called a word.
Learn more…13 questions
Sort by count of
-
23
votes1
answer1194
viewsRegular expression to recognize language: words that do not contain "bbab"
The @LINQ challenged me to write a regular expression to recognize the following language L: I was able to assemble, on this premise, the following finite state machine: the Miguel Angelo detected a…
regex mathematics computer-theory automata formal-languagesasked 7 years, 1 month ago Jefferson Quesado 22,370 -
21
votes2
answers5427
viewsWhat is an automaton?
For several times I hear discussions about automata, whether in the chat or in questions/answers. However I particularly do not know what an automaton is, I have no idea to tell the truth. When…
-
15
votes1
answer229
viewsIs a finite state machine capable of detecting the primality of a number?
I recently saw a publishing how they taught Perl to recognize a prime number using regular expressions. The regular expression in question is: /^1?$|^(11+?)\1+$/ The only requirement of this regular…
regex mathematics computer-theory automata formal-languagesasked 4 years, 9 months ago Jefferson Quesado 22,370 -
10
votes1
answer886
viewsWhat is the difference between automata and grammars?
I am studying about compilers and relating programming languages. What is the difference between automata and grammars?
-
9
votes1
answer1654
viewsWhat is a cellular automaton?
What is the cellular automaton about? What kind of problem can it solve? It’s something equivalent to turing machines?
-
5
votes2
answers1470
viewsWhat is the real meaning of using ε-transitions in NFA?
Well, I still don’t understand the logic of using ε-transitions in NFA, what is the real meaning? Jump from state without making a reading? For example, given the regex: a* NFA: DFA:…
automataasked 10 years, 4 months ago Victor Martins 798 -
5
votes1
answer425
viewsWhat is the Pumping Lemma (or Pumping Lemma) ? And how to apply it?
I was reading by HOPCROFT and had difficulty applying the pumping lemma in a formal way to exercises to prove that a language is not regular. In this case, I refer to the Pumping Motto for regular…
-
5
votes1
answer1014
viewsDifference between 'Regular language' for 'irregular language'
Reading a question about basic programming concepts, I come across the following statement: Let A and B be two languages over the binary alphabet, that is, over the alphabet composed only of 0’s and…
computer-science computer-theory automata formal-languagesasked 5 years, 10 months ago Luiz Augusto 2,482 -
4
votes1
answer503
viewsWhat simulate, NFA or DFA?
Well, we know that theoretically and practically, every NFA can be converted to a DFA that accepts the same language. My question is this:: Which one should I actually simulate? NFA or DFA? I don’t…
automataasked 10 years, 3 months ago Victor Martins 798 -
4
votes2
answers330
viewsHow is the find function implemented?
Unlike match() looking for an occurrence of a language y in the beginning of the string, the find() makes a quest for y inside that string. I could use the algorithm of Knuth-Morris-Pratt to search…
-
3
votes1
answer460
viewsWhat are the differences between the computational power of deterministic and non-deterministic stack automata?
There is computational power difference between a deterministic stack automaton and a non-deterministic automaton?
-
3
votes1
answer1775
viewsHow to turn a context-free grammar into a stack automaton?
I have a grammar, like for example: Or else: Or even that: Or this grammar, which represents the boolean logic for three variables: How to turn these grammars into stack automata? Would have some…
algorithm computer-theory automata formal-languagesasked 7 years, 1 month ago Jefferson Quesado 22,370 -
2
votes1
answer45
viewsHelps with understanding cellular automaton code
I would like you to help me understand a code for calculating and presenting cellular automata that I found on the Internet. The code in question is as follows:: #include <stdio.h> #include…