I'm studying for a finite automata & grammars test and I'm stuck with this question: Construct a grammar that generates L: L = {a^n b^m c^m+n|n>=0, m>=0} I believe my productions shoul...

I'm working on a problem (from Introduction to Automata Theory, Languages and Computer by Hopcroft, Motwani and Ullman) to write a regular expression that defines a language consisting of all strin...

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

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?

Can´t find anything affirmative about it. And a NFA with any epsilon transition is a epsilon-NFA ? Thanks.

While practicing for my final exams I found this question in Automata Theory, Language and Computation by J. Hopcroft, R. Motwani, J. Ullman on page 222. PDA should accept string in which the coun...

I have some badly formatted XML that I must parse. Fixing the problem upstream is not possible. The (current) problem is that ampersand characters are not always escaped properly, so I need to con...

Good Day everyone! I am trying to solve this Exercise for learning purpose. Can someone guide me in solving these 3 questions? Like I tried the 1st question for addition of 2 binary numbers sepa...

Produce a PDA to recognise the following language : the language of strings containing more a's than b's I have been struggling with this question for several days now, I seem to have hit a com...

I was looking at the question posed in this stackoverflow link (Regular expression for odd number of a's) for which it is asked to find the regular expression for strings that have odd number o...

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

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

I have 2 simple lexer rules in my ANTLR4 grammar: fragment Attrs : '.' ARCH; fragment ARCH : 'IA32' | 'X64' | 'IPF' | 'EBC' | 'common'; The generated ATN with ANTLR4.7 is like this (Visual Studio...

Can we use a factor-oracle with suffix link (paper here) to compute the longest common substring of multiple strings? Here, substring means any part of the original string. For example "abc" is the...

Good afternoon, Does anyone know of an "out-of-the-box" implementation of Levenshtein DFA (deterministic finite automata) in .NET (or easily translatable to it)? I have a very big dictionary with ...

We all know that (a + b)* is a regular language for containing only symbols a and b. But (a + b)* is a string of infinite length and it is regular as we can build a finite automata, so it should b...

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

So I'm studying for a test I have coming up on pushdown automata and context-free languages and I'm stuck on this one construction. I have every part of this automaton completely working perfectl...

Recently I faced the problem for finding first and follow S->cAd A->Ab|a Here I am confused with first of A which one is correct {a} , {empty,a} as there is left recursion in A's producti...

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

I'm really new to this stuff so I apologize for the noobishness here. construct a Deterministic Finite Automaton DFA recognizing the following language: L= { w : w has at least two a's and an o...

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

How can a formal context free grammar be generated for the following language: {ai bjck | i != j or j != k} I have following productions but can't understand it: S->AX | YC unequal b’s c...

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

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://el...