Questions tagged [fl.formal-languages]
formal languages, grammars, automata theory
401
questions
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 ...
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 ...
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).
...
42
votes
10answers
16k views
Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?
Real computers have limited memory and only a finite number of states.
So they are essentially finite automata.
Why do theoretical computer scientists use the Turing machines
(and other equivalent ...
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 ...
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 ...
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.
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
4answers
6k views
What is the most powerful kind of parser?
As a side-project, I'm writing a language using Python. I started by using a flex/bison clone called Ply, but am coming up against the edges in the power of what I can express with that style of ...
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 ...
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 ...
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 ...
28
votes
3answers
4k views
Known algorithms to go from a DFA to a regular expression
I was wondering whether there is a ``better'' (I will explain in what sense) algorithm to start from a DFA $\mathcal{A}$ and construct a regular expression $r$ such that $L(\mathcal{A})=L(r)$, than ...
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 ...
28
votes
2answers
2k views
How many DFAs accept two given strings?
Fix an integer $n$ and alphabet $\Sigma=\{0,1\}$. Define $DFA(n)$ to be the collection of all finite-state automata on $n$ states with starting state 1. We are considering all DFAs (not just connected,...
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 ...
26
votes
1answer
683 views
Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?
We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
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" ...
25
votes
3answers
2k views
Does there exist an extension of regular expressions that captures the context free languages?
In many papers involving context-free grammars (CFGs), the examples of such grammars presented there often admit easy characterizations of the language they generate. For example:
$S \to a a S b$
...
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, ...
24
votes
1answer
527 views
complexity of the half language
For any language $L$ over $\Sigma^*$, define
$$L_{1/2} = \{x \in \Sigma^* : xy\in L, y\in\Sigma^{|x|} \}.$$
In words, $L_{1/2}$ consists of all $x$ for which there is a $y$ of equal length such that $...
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 ...
22
votes
1answer
2k views
Can all unambiguous grammars be parsed in linear time?
When tinkering with noncanonical LR parsing, I thought up a parsing method (with infinitely sized tables, which makes it somewhat unpractical) capable of parsing exactly the unambiguous grammars in $O(...
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 ...
21
votes
3answers
3k views
Regular languages from category-theoretical point of view
I noticed that regular languages over the alphabet $\Sigma$ can be naturally thought of as a poset, and indeed a lattice. Moreover, concatenation together with the empty language $\epsilon$ defines a ...
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 ...
21
votes
4answers
6k views
Proof of the pumping lemma for context-free languages using pushdown automata
The pumping lemma for regular languages can be proved by considering a finite state automaton which recognizes the language studied, picking a string with a length greater than its number of states, ...
21
votes
3answers
758 views
Complexity of intersection of regular languages as context-free grammars
Given regular expressions $R_1, \dots, R_n$, are there any non-trivial bounds on the size of the smallest context-free grammar for $R_1 \cap \cdots \cap R_n$?
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 ...
20
votes
5answers
2k views
A special class of languages: “circular” languages. Is it known?
Define the following class of "circular" languages over a finite alphabet Sigma. Actually, the name already exists to denote a different thing it seems, used in the field of DNA computing. AFAICT, ...
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 ...
20
votes
0answers
638 views
Why is the Pumping Lemma sometimes called Bar-Hillel's Lemma?
There are several papers in the literature that refer to the Pumping Lemma for context free languages as Bar-Hillel's Lemma (for example, here, here, and on the Wikipedia page). However, the first ...
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 ...
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'...
19
votes
2answers
1k views
Status of Cerny Conjecture?
A DFA has a synchronizing word if there is a string that sends any state of the DFA to a single state. In ‘The Cerny Conjecture for Aperiodic Automata” by A. N. Trahtman (Discrete Mathematics and ...
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,...
19
votes
2answers
441 views
“Embedding” a language in itself
Main/General Question
Let $L$ be a language. Define the languages $L_i$ with $L_0 = L$ and
$$L_i = \{xwy : xy \in L_{i-1}, w \in L\}$$
for $i \geq 1$. Consider $\hat{L} = \bigcup L_i$. So, we ...
19
votes
1answer
931 views
Is equivalence of unambiguous context-free languages decidable?
It is well known that the equivalence problem is undecidable for general context-free languages. However, all proofs of this fact that I am aware of seem to involve some ambiguous context-free ...
18
votes
3answers
679 views
CFG parsing using $o(n^2)$ space
There are a multitude of algorithms that can parse a context-free grammar in $O(n^3)$ time. Using matrix multiplication, one can even go asymptotically faster than that.
However, all algorithms for ...
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 ...
18
votes
3answers
3k views
Generalizations of Brzozowski's method of derivatives of regular expressions to grammars?
Brzozowski's method of derivatives is a very pretty technique for building deterministic automata from regular expressions in a nicely algebraic way. I've worked out some cute generalizations of this ...
18
votes
2answers
682 views
Deciding whether a unary context-sensitive language is regular
It is a well-known result that the question
Does a context-free grammar generate a regular language?
is undecidable. However, it becomes decidable on a unary alphabet, simply because in this case,...
18
votes
1answer
806 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$], ...
17
votes
1answer
297 views
Is the Set of all Primitive Words a Prime Language?
A word $w$ is called primitive, if there is no word $v$ and $k > 1$ so that $w = v^k$.
The set $Q$ of all primitive words over an alphabet $\Sigma$ is a well known language. WLOG we can choose $\...
17
votes
2answers
443 views
Unary languages recognized by two-way deterministic counter automata
2dca's (two-way deterministic one-counter automata) (Petersen, 1994) can recognize the following unary language:
\begin{equation}
\mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace.
\end{...
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 ...
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 ...
16
votes
1answer
1k views
Efficient concatenation of DFAs?
There is theoretical evidence that the naive cartesian-product construction for the intersection of DFAs is "the best we can do". What about the concatenation of two DFAs? The trivial construction ...
16
votes
1answer
788 views
Completeness and Context-Sensitive Languages.
I'm interested in two questions regarding context-sensitive languages (CSL) and completeness:
Is there a notion of completeness for CSL, and which languages are complete?
Are there natural CSL that ...
