dfa Questions
6
I'm currently working on a scanner generator.
The generator already works fine. But when using character classes the algorithm gets very slow.
The scanner generator produces a scanner for UTF8 en...
2
How can I prove if L = {a^n b^m | n>m} is a regular or irregular language?
Doha asked 2/3, 2013 at 11:46
7
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?
Complice asked 8/2, 2016 at 14:56
4
Solved
Can´t find anything affirmative about it. And a NFA with any epsilon transition is a epsilon-NFA ?
Thanks.
Seldon asked 9/12, 2012 at 20:0
2
Solved
I have a little confusion in checking whether the given language is regular or not using pumping lemma.
Suppose we have to check whether:
L. The language accepting even number of 0's in regular...
Orin asked 5/2, 2013 at 10:18
3
Solved
Can someone much brighter than I succinctly describe to the SO community the NFA to DFA conversion algorithm? (Preferably in 500 words or less.) I've seen diagrams and lectures that have only serve...
Oliverolivera asked 15/12, 2010 at 14:53
3
Solved
This is a theoretical Computer Science question (Computation Theory).
I know that RegExps can take a very long time to calculate. However, from Theory of Computation we know that matching with a R...
Swill asked 30/8, 2019 at 18:45
2
Solved
I have a DFA (Q, Σ, δ, q0, F) with some “don't care transitions.” These transitions model symbols which are known not to appear in the input in some situations. If any such transition i...
Frisco asked 3/7, 2019 at 12:48
3
Solved
My problem may sounds different to you.
I am a beginner and I am learning Finite Automata. I am googing over Internet to find the
Regular Expression for Finite Automata of Given Machine Below.
...
Sputter asked 2/7, 2013 at 7:56
2
Solved
This is the DFA i have drawn-
Is it correct?
I am confused because q4 state has 2 different transitions for same input symbol which violates the rule of DFA, but I can't think of any other solut...
Republic asked 2/1, 2013 at 13:15
3
Solved
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...
4
Solved
I am self-studying regular expressions and found an interesting practice problem online that involves writing a regular expression to recognize all binary numbers divisible by 3 (and only such numb...
5
Solved
I am looking for a non-technical explanation of the difference between DFA vs NFA engines, based on their capabilities and limitations.
Topeka asked 20/10, 2010 at 13:38
4
Solved
I'm looking for an implementation of regular expression matching that operates on a stream of data -- i.e., it has an API that allows a user to pass in one character at a time and report when a mat...
2
Solved
I read that every Non-deterministic Finite Automaton (NFA) can be transferred into a Deterministic Finite Automaton (DFA). Can this be done for kleene star regex, say a*?
Above is the NFA for a*....
Protoactinium asked 24/1, 2016 at 1:48
5
Solved
In DFA we can do the intersection of two automata by doing the cross product of the states of the two automata and accepting those states that are accepting in both the initial automata.
Union is p...
Maclaine asked 9/2, 2014 at 16:58
4
Solved
I have trouble understanding how to compute the lookaheads for the LR(1)-items.
Lets say that I have this grammar:
S -> AB
A -> aAb | a
B -> d
A LR(1)-item is an LR(0) item with a look...
Airdrome asked 31/12, 2012 at 15:12
1
Solved
I am looking for a discussion on which is better used and in what circumstances in a compiler an nfa or dfa. what are the time complexity trade-offs of simulating an nfa vs dfa and which one is mor...
Shari asked 2/1, 2011 at 21:37
1
Solved
I am referring to the outline of the Knuth-Morris-Pratt (KMP) algorithm for substring search in Sedgewick's book "Algorithms" (4th ed.).
The KMP algorithm uses a backup in substring search based o...
Eructate asked 30/5, 2015 at 15:52
7
Solved
The DFA must have the following four properties:
The DFA has N nodes
Each node has 2 outgoing transitions.
Each node is reachable from every other node.
The DFA is chosen with perfectly uniform r...
Amuse asked 2/4, 2011 at 20:24
2
Is it possible to implement capture groups with DFA-based regular expressions while maintaining a linear time complexity with respect to the input length?
Intuitively I think not, because the subs...
Godfearing asked 9/3, 2015 at 11:55
1
In modding a closed-source game I'm modifying the machine code at runtime to jmp into my own code. To do this in a generic manner I'm using pattern matching to find the code locations I want to mod...
Cyanamide asked 22/12, 2014 at 22:27
1
I'm interested in learning how to write a lexer generator like flex. I've been reading "Compilers: Principles, Techniques, and Tools" (the "dragon book"), and I have a basic idea of how flex works....
Bos asked 1/6, 2014 at 5:32
1
Solved
When you read such posts as Regex: NFA and Thompson's algorithm everything looks rather straightforward until you realize in real life you need not only direct characters like "7" or "b", but also:...
1
Solved
Having the diagram of a DFA, how can I convert it to a Turing Machine? Do I have to find the language that the DFA accepts and then create the Turing Machine? Or is there a direct way?
Thank you.
...
Aimless asked 11/12, 2013 at 0:57
1 Next >
© 2022 - 2024 — McMap. All rights reserved.