First, this is not a question asking for the algorithm to convert a NFA to DFA. It's known (and proved) that the equivalent DFA of a NFA has at most 2n states, even though most of the times it wil...

So this is not about the pumping lemma and how it works, it's about a pre-condition. Everywhere in the net you can read, that regular languages must pass the pumping lemma, but noweher anybody tal...

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

I'm trying to a develop a simulation that executes a non deterministic finite automaton in Java. The first command line argument is a text file that defines the machine. The second argument is an i...

Given the following language: L1 = { (ab)n | n ≥ 0 } That is, L1 = { ε ab, abab, ababab, abababab, ... } The question is to find what language L12 is. My guess is that it's equal...

It is well-known how one gets from an NFA for a regular language to a minimal DFA. However, the DFA might have an exponentially larger number of states. What I need is a way to reduce an NFA, givi...

I'm working with Ragel to evaluate FSAs, and I want to embed a user action that runs whenever my machine finishes testing the input. I need this action to run regardless of whether or not the machi...

The gist of my question is that I have a deterministic state automata that is transitioning according to a list of moves, and I want this sequence of transition to serve as a "computational context...

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

Given: I have no idea what the accepted language is. From looking at it you can get several end results: 1.) bb 2.) ab(a,b) 3.) bbab(a, b) 4.) bbaaa

In the Chomsky classification of formal languages, I need some examples of Non-Linear, Unambiguous and also Non-Deterministic Context-Free-Language(N-CFL)? Linear Language: For which Linear gramm...

I am currently looking into the problem of regular expressions which can end up running in exponential time when matched against a certain input, for example both (a*)* and (a|a)* potentially exhib...

Does anyone have a solution for a basic, compact Finite state machine/automata written in Objective-C code? I am interested in reusable components so that the FSM have states added and actions def...

i want to draw an automata with edges and circulaire states, something like this http://pop-art.inrialpes.fr/~girault/Cours/Automates/td5.html, have u an example for that

What would be the most complete finite automata library for Python, which is able to do the basic manipulations such as: Minimization, Determinization of Nondeterministic Finite automata Union, I...

Nearly all programming languages used are Turing Complete, and while this affords the language to represent any computable algorithm, it also comes with its own set of problems. Seeing as all the a...

It's feel like I'm stuck, my friends. Can somebody explain me pick equations from "Pearls of Functional Algorithm Design", chapter 11 ("Not the maximum segment sum"). Here is the problem (a littl...

I am now taking a course on Theory of Computation. I can understand the concepts well. I can able to solve the problems. And, when I asked my instructor about the real world application, he told me...

I'm looking for ways to de-spaghttify my front-end widget code. It's been suggested that a Finite State Machine is the right way to think about what I'm doing. I know a State Machine paradigm can b...

I have a problem which has an solution that can be solved by iteration, but I'm wondering if there's a more elegant solution using regular expressions and split() I have a string (which excel is p...

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

I am searching for a free tool(s) to create visually appealing diagrams of finite automata and syntax trees. Note: I really just want to draw diagrams. I do not have to create a model or do s...

I have been working on a project for a month or so now to develop a XML validator (XSD) in javascript. I have gotten really close but keep running into problems. The only thing I have working wel...

This question may sound cliched, but I am in a situation here. I am trying to implement a finite state automaton to parse a certain string in C. As I started writing the code, I realised the code...

I want to test whether two languages have a string in common. Both of these languages are from a subset of regular languages described below and I only need to know whether there exists a string in...