I have a question about DFA minimization. So I've used very well known techniques to convert regular expression into NFA and then construct DFA from it, using goto / closure algorithm. Now the ques...

Suppose you have a language where identifiers might begin with keywords. For example, suppose "case" is a keyword, but "caser" is a valid identifier. Suppose also that the lexer rules can only hand...

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 ...

How do you say δ: Q × Σ → Q in English? Describing what × and → mean would also help.

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, s...

Using pumping lemma, we can easily prove that the language L1 = {WcW^R|W ∈ {a,b}*} is not a regular language. (the alphabet is {a,b,c}; W^R represents the reverse string W) However, If we replace ...

(I'm just learning how to write a compiler, so please correct me if I make any incorrect claims) Why would anyone still implement DFAs in code (goto statements, table-driven implementations) when ...

What is the direct and easy approach to draw minimal DFA, that accepts the same language as of given Regular Expression(RE). I know it can be done by: Regex ---to----► NFA ---to-----► DFA ---to--...

I'm writing an implementation of deterministic finite automata for some research project and there are some arcs which lead to the same state. I wrote this class for State , but I wonder why the co...

Lexer DFA results in "code too large" error I'm trying to parse Java Server Pages using ANTLR 3. Java has a limit of 64k for the byte code of a single method, and I keep running into a "code too...

I'm currently trying to come up with a data structure that fits the needs of two automata learning algorithms I'd like to implement in Haskell: RPNI and EDSM. Intuitively, something close to what ...

I'm doing an assignment for automata theory, which I have to determine whether a word is accepted or not by a transition function for a deterministic finite automaton I have this input file: 6 8 ...

I'm looking to implement a DFA minimizer in my lexer, but I can't seem to produce a DFA that doesn't look like it's already the minimal DFA for the expression. I'm constructing the DFA from a NFA ...

i want to write a program that convert nfa to dfa , user draw a graph then Program convert it to dfa . how can i do it?

I'm wondering how to find a set of all matches to a given regex with a finite number of matches. For example: All of these example you can assume they start with ^ and end with $ `hello?` -> ...

I have a remote "agent" that returns "yes" or "no" when handed a string. Communicating with this agent is expensive, so I'm hoping to find a library that will allow me to iteratively build a regula...

Are there any (free) regular expression engines for Java, that can compile a regular expression to a DFA, and do group capturing while matching the DFA ? I've found dk.brics.automaton and jrexx, w...

Does anyone have a straightforward description of the algorithm for constructing the union of two given DFA's? For example, say we have two DFA's over {0,1} where {w|w has an odd number of charact...

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 a...

I'm reading about compilers and parsers architecture now and I wonder about one thing... When you have XML, XHTML, HTML or any SGML-based language, what would be the role of a lexer here and what w...

I have this input file: 2 3 2 1 ab 1 0 2 0 2 0 2 0 3 abaa aab aba 3 3 2 ade 0 1 2 1 2 0 2 1 0 1 2 2 2 a de The first line represents the number of test cases. Each test case starts with 3 inte...

I have a given DFA that represents a regular expression. I want to match the DFA against an input stream and get all possible matches back, not only the leftmost longest match. For example: regex: ...

Is there a way to find out if two arbitrary regular expressions are equivalent? Looks like complex problem to me, but there might be some DFA simplification mechanism or something?