Stack Overflow
Stack Overflow

Questions tagged [automata]

In theoretical computer science, automata theory is the study of abstract 'mathematical' machines or systems and the computational problems that can be solved using these machines. These abstract machines are called automata. ("Automata", Wikipedia)

From Wikipedia,

Automata, or automata theory, is the study of mathematical objects called abstract machines or automata and the computational problems that can be solved using them. Automata comes from the Greek word αὐτόματα meaning "self-acting".

692 questions
116
votes
8 answers

Regular vs Context Free Grammars

I'm studying for my computing languages test, and there's one idea I'm having problems wrapping my head around. I understood that regular grammars are simpler and cannot contain ambiguity, but can't do a lot of tasks that are required for…
Jason Baker
  • 192,085
  • 135
  • 376
  • 510
109
votes
10 answers

Is it possible for a computer to "learn" a regular expression by user-provided examples?

Is it possible for a computer to "learn" a regular expression by user-provided examples? To clarify: I do not want to learn regular expressions. I want to create a program which "learns" a regular expression from examples which are interactively…
Daniel Rikowski
  • 71,375
  • 57
  • 251
  • 329
87
votes
3 answers

Design DFA accepting binary strings divisible by a number 'n'

I need to learn how to design a DFA such that given any number 'n', it accepts binary strings {0, 1} whose decimal equivalent number is divisible by 'n'. There will be different DFAs for different 'n', but can somebody give a basic approach that I…
Naveen
  • 1,193
  • 4
  • 13
  • 17
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

Grammatical inference of regular expressions for given finite list of representative strings?

I'm working on analyzing a large public dataset with lots of verbose human-readable strings that were clearly generated by some regular (in the formal language theory sense) grammar. It's not too hard to look at sets of these strings one by one to…
Stephen Lin
  • 5,470
  • 26
  • 48
22
votes
6 answers

Design Pattern problem involving N states and transitions between them

I have a problem at hand and I am not getting which design pattern to use. The problem goes as such: I have to build a system which has 'N' states and my system has to do a transition from any state to any other state depending on some conditions.…
Amit
  • 435
  • 2
  • 8
  • 16
21
votes
9 answers

Is Automata Theory dead?

I loved the course I took in Automata Theory and Formal Languages, so naturally I started looking around the interwebs to learn what happened since the time the books on which the course was based were written. What I discovered was that the list…
EpsilonVector
  • 3,973
  • 7
  • 38
  • 62
19
votes
14 answers

Code Golf: Automata

I made the ultimate laugh generator using these rules. Can you implement it in your favorite language in a clever manner? Rules: On every iteration, the following transformations occur. H -> AH A -> HA AA -> HA HH -> AH AAH -> HA HAA -> AH n…
Unknown
  • 45,913
  • 27
  • 138
  • 182
19
votes
2 answers

What exactly is the 'pumping length' in the Pumping lemma?

I'm trying to understand what is this 'magical' number 'n' that is used in every application of the Pumping lemma. After hours of research on the subject, I came to the following website: http://elvis.rowan.edu/~nlt/TheoryNotes/PumpingLemma.pdf It…
Ivan Prodanov
  • 34,634
  • 78
  • 176
  • 248
18
votes
5 answers

Is there a good graph layout library callable from C++?

The (directed) graphs represent finite automata. Up until now my test program has been writing out dot files for testing. This is pretty good both for regression testing (keep the verified output files in subversion, ask it if there has been a…
user180247
18
votes
1 answer

Finding the complement of a DFA?

I am asked to show DFA diagram and RegEx for the complement of the RegEx (00 + 1)*. In the previous problem I had to prove that the complement of a DFA is closed and is a regular expression also, so I know that to convert a DFA, M to the complement,…
Matt Hintzke
  • 7,744
  • 16
  • 55
  • 113
13
votes
4 answers

Can a DFA have epsilon/lambda transitions?

Can´t find anything affirmative about it. And a NFA with any epsilon transition is a epsilon-NFA ? Thanks.
liwing
  • 211
  • 2
  • 3
  • 8
13
votes
6 answers

Advanced Formal logic / Automata Theory textbook

I know this is more a Math/Formal Language/Automata/Computer science question than an a programming one, but I hope I can get some advice on a comprehensible textbook (not an indecipherable monograph) on formal logic beyond Propositional and…
anno
  • 5,970
  • 4
  • 28
  • 37
12
votes
1 answer

NFA/DFA implementation in C#

Does anyone know of any good NFA and DFA implementation in C#, possibly implementing as well conversions between both? What I would like would be to be able to construct a NFA and then convert it automatically to a DFA, but without having to write…
Miguel
  • 3,466
  • 8
  • 38
  • 67
11
votes
4 answers

Convert regular expression to CFG

How can I convert some regular language to its equivalent Context Free Grammar? Is it necessary to construct the DFA corresponding to that regular expression or is there some rule for such a conversion? For example, consider the following regular…
Prasoon Saurav
  • 91,295
  • 49
  • 239
  • 345
1
2 3
…
46 47