Questions tagged [fl.formal-languages]
formal languages, grammars, automata theory
73
questions
45
votes
4answers
10k views
Is finding the minimum regular expression an NP-complete problem?
I am thinking of the following problem:
I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses).
...
21
votes
2answers
3k views
computing the minimal NFA for a DFA
Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known ...
9
votes
1answer
736 views
Do there exists polynomial size CFG that describe this finite language?
Do there exists permutations $\pi_1,\pi_2$ and polynomial size (in $|w|=n$) context free grammar that describe the finite language $\{w \pi_1(w) \pi_2(w)\}$ over alphabet $\{0,1\}$?
UPDATE: For one ...
251
votes
11answers
97k views
What is the enlightenment I'm supposed to attain after studying finite automata?
I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we ...
33
votes
11answers
27k views
Books on automata theory for self-study
I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams.
47
votes
5answers
7k views
Is the Chomsky-hierarchy outdated?
The Chomsky(–Schützenberger) hierarchy is used in textbooks of theoretical computer science, but it obviously only covers a very small fraction of formal languages (REG, CFL, CSL, RE) compared to the ...
28
votes
5answers
4k views
Counting words accepted by a regular grammar
Given a regular language (NFA, DFA, grammar, or regex), how can the number of accepting words in a given language be counted? Both "with exactly n letters" and "with at most n letters" are of ...
15
votes
1answer
413 views
Lower bounds on the size of CFGs for specific finite languages
Consider the following natural question: Given a finite language $L$, what is the smallest context-free grammar generating $L$?
We can make the question more interesting by specifying a sequence of ...
19
votes
1answer
2k views
What is the number of languages accepted by a DFA of size $n$?
The question is simple and direct: For a fixed $n$, how many (different) languages are accepted by a DFA of size $n$ (i.e. $n$ states)? I will formally state this:
Define a DFA as $(Q,\Sigma,\delta,...
38
votes
14answers
25k views
How practical is Automata Theory?
There is always a way for application in topics related to theoretical computer science. But textbooks and undergraduate courses usually don't explain the reason that automata theory is an important ...
39
votes
6answers
6k views
Regular expressions aren't
Ask even someone with a background in computer science what a regular expression is, and the answer is likely to go beyond the constraint of being within reach of a finite-state automaton.
For ...
19
votes
3answers
1k views
Is the concept of the Turing Machine derived from automata?
I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"?
I didn't know the answer of course, but I'...
20
votes
1answer
1k views
Number of words of length n in a context-free language
Denote by $w_n$ the number of words of length $n$ in a (possibly ambiguous) context-free language.
What is known about $w_n$?
I'm sure this has been studied a lot, but I couldn't find anything at ...
16
votes
2answers
923 views
Collatz Conjecture & Grammars / Automata
I was wondering if there is a good bibliography of attempts to investigate the Collatz conjecture as a formal grammar? (or any other attempts in the CS community to deal with this class of generative ...
15
votes
2answers
634 views
Regular versus TC0
According to the Complexity Zoo,
$\mathsf{Reg} \subseteq \mathsf{NC^1}$ and
we know that $\mathsf{Reg}$ cannot count so $\mathsf{TC^0} \not\subseteq \mathsf{Reg}$.
However it doesn't say if $\mathsf{...
14
votes
0answers
2k views
minimizing size of regular expression
Suppose we have a regular language specified by a regex, for example, (ab|ac)* and we wish to find an equivalent regex with the minimal number of symbols, (a(b|c))*. Is there any efficient way to do ...
-2
votes
1answer
518 views
Decidability of “does this CFG define a regular language”
Is the decidablity of the following question known?
Given a CFG G, is L(G) regular?
I've seen a bunch of decidability results in the world of CFLs, but I don't think I've ever seen this one, and can'...
25
votes
6answers
2k views
Advanced techniques for determining complexity lower bounds
Some of you may have been following this question, which was closed due to not being research level. So, I'm extracting the part of the question which is at a research level.
Beyond the "simpler" ...
18
votes
6answers
1k views
Which models of computation can be expressed through grammars?
This is a reformulation of Are grammars programs? previous asked by Vag and with many suggestions from the commenters.
In what way can a grammar be seen as specifying a model of computation?
If, for ...
28
votes
2answers
2k views
Conditions for NFA universality
Consider a nondeterministic finite automata $A = (Q, \Sigma, \delta, q_0, F)$, and a function $f(n)$. Additionally we define $\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i$.
Now lets analyze the ...
25
votes
5answers
3k views
Recovering a parse forest from an Earley parser?
I was recently reading up on the Earley parser and think it's one of the most elegant algorithms I've seen to date. However, the algorithm in its traditional sense is a recognizer and not a parser, ...
23
votes
1answer
709 views
Languages recognized by polynomial-size DFAs
For a fixed finite alphabet $\Sigma$, a formal language $L$ over $\Sigma$ is regular if there exists a deterministic finite automaton (DFA) over $\Sigma$ which accepts exactly $L$.
I am interested in ...
22
votes
4answers
3k views
Where do most REGEX implementations fall on the complexity scale?
Most modern implementations of regular expressions, such as the ones in perl or .NET, go beyond the classical computer science definition of REGEXes with features like lookahead and lookbehind. Do ...
26
votes
2answers
2k views
Context Sensitive Grammars and Types
1) What, if any, is the relationship between static typing and formal grammars?
2) In particular, would it be possible for a linear bounded automaton to check whether, say, a C++ or SML program was ...
19
votes
5answers
726 views
What notable automaton models have polynomially-decidable containment?
I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if ...
10
votes
5answers
4k views
Automata Theory / Formal Language Thesis Topic
Hey All,
I'm currently trying to find a solid masters thesis topic pertaining to some branch of automata theory or related to formal languages. I'm trying to generate some good ideas for what an ...
31
votes
1answer
779 views
Eilenberg's rational hierarchy of nonrational automata & languages — where is it now?
In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D dealing with "a hierarchy (called the rational ...
30
votes
2answers
2k views
Is {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} non-context-free?
Is the language {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} context-free or not?
I realized that I have encountered almost all variants of this question with different conditions about the ...
16
votes
1answer
364 views
Compared growth of the number of syntactic classes and Nerode classes.
For a language L ⊆ Σ^*, define the syntactic congruence ≡ of L as the least congruence on Σ^* that saturates L, i.e. :
u ≡ v ⇔ (∀ x, y)[xuy ∈ L ↔ xvy ∈ L].
Now define the Nerode equivalence as the ...
14
votes
4answers
590 views
Base-k representations of the co-domain of a polynomial - is it context-free?
In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is listed as open:
Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ for ...
12
votes
3answers
424 views
Is the complement of { www | … } context-free?
It is well-known that the complement of $\{ ww \mid w\in \Sigma^*\}$ is context-free. But what about the complement of $\{ www \mid w\in \Sigma^*\}$?
8
votes
8answers
6k views
What are the simplest turing-complete systems? [closed]
Lambda Calculus is very simple. Are there even simpler turing-complete systems? Which is the simplest of them all?
3
votes
0answers
348 views
Are grammars programs? [closed]
Are grammars programs? That is, are languages for grammar specification programming languages?
Update.
Motivation for the question is follows:
To know whether languages for grammars are programming ...
30
votes
4answers
1k views
Are there “small” machines which can efficiently match regular expressions?
It's well-known that a regular expression can be recognized by a nondeterministic finite automaton of size proportional to the regular expression, or by a deterministic FA which is potentially ...
22
votes
2answers
1k views
Protocol partition number and deterministic communication complexity
Besides (deterministic) communication complexity $cc(R)$ of a relation $R$, another basic measure for the amount of communication needed is the protocol partition number $pp(R)$. The relation between ...
20
votes
2answers
6k views
Is JSON a Regular Language?
I was wondering if the JSON spec defined a regular language. It seems simple enough, but I'm not sure how to prove it myself.
The reason I ask, is because I was wondering if one could use regular ...
12
votes
1answer
2k views
Which formal language class are XML and JSON with unique keys?
I moved this question from stackoverflow where id got no answers. We had a similar question whether JSON is regular:
JSON and XML are both frequently called to be context-free languages - they are ...
6
votes
7answers
1k views
What are regular expressions good for?
If you ask a question about parsing HTML with regex, you will certainly be referenced to this famous rant. Though there is not a canonical rant for it, I've also been told that regex aren't powerful ...
16
votes
2answers
617 views
How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?
Unambiguous Finite Automatons (UFA) are special type of non-deterministic finite automatons (NFA).
A NFA is called unambiguous if every word $w\in \Sigma^*$ has at most one accepting path.
This ...
14
votes
3answers
849 views
The significance of state complexity in automata and regular languages?
I'm reading "Concatenation of Regular Languages and Descriptional Complexity" by Galina Jiraskova, 2009 on the state complexity resulting from concatenation of two regular languages ( by Galina ...
12
votes
0answers
1k views
Is CFL strictly contained in NL?
We know that $\mathsf{REG}=\mathsf{NSPACE}(O(1))$ and $\mathsf{CSL}=\mathsf{NSPACE}(O(n))$.
What is the relation of $\mathsf{CFL}$ and $\mathsf{NSPACE}(O(\log n))=\mathsf{NL}$?
Is $\mathsf{CFL}$ a ...
12
votes
0answers
315 views
Survey on infinite alphabet automata?
The paper "Symbolic Finite State Transducers, Algorithms and Applications" by Bjorner et al (to appear at POPL 2012) describes one type of finite-state, infinite-alphabet automata/transducers by using ...
8
votes
1answer
373 views
Lower bound for NFA accepting 3 letter language
Related to a recent question (Bounds on the size of the smallest NFA for L_k-distinct) Noam Nisan asked for a method to give a better lower bound for the size of an NFA than what we get from ...
18
votes
1answer
805 views
Context-sensitive grammar for SAT?
By a classic result of Kuroda, the complexity class NSPACE[$n$] (also known as NLIN-SPACE) is precisely the class CSL of context-sensitive languages. The satisfiability problem SAT is in NSPACE[$n$], ...
12
votes
3answers
389 views
Does there exist a hardest DCFL?
Greibach famously defined a language $H$, the so-called nondeterministic version of $D_2$, such that any CFL is an inverse morphic image of $H$. Does there exist a similar statement with DCFL, ...
12
votes
2answers
2k views
Post Correspondence Problem variant
This is probably pretty simple, but consider the standard Post Correspondence Problem:
Given $\alpha_1, \ldots, \alpha_N$ and $\beta_1, \ldots, \beta_N$, find a sequence of indices $i_1, \ldots, i_K$ ...
10
votes
3answers
617 views
Maximum shortest word accepted by pushdown automata
Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic ...
9
votes
0answers
340 views
Deciding if a language induced by a Presburger formula is context-free
Is the following problem decidable?
Given $n$ and a Presburger arithmetic formula $\phi(x_1,x_2,\dots,x_n)$, determine whether the language $\{a_1^{i_1} \dots a_n^{i_n}:\phi(i_1,i_2,\dots,i_n)\}$ ...
7
votes
1answer
547 views
On the relation for the Myhill-Nerode theorem/syntactic monoid of a language
In order to characterize regular languages one finds the following definition useful:
Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. Say that $x,y\in\Sigma^*$ are $\equiv_L$-related, and ...
7
votes
1answer
511 views
Shortest string in the intersection of a context-free language and a regular language
For a language $X$, define $ss(X) = \min_{x\in X} |x|$, the length of the shortest string in $X$. For simplicity, we define $ss(\emptyset)=0$.
Let $L$ be a context-free language generated by a context-...
