Questions tagged [fl.formal-languages]
formal languages, grammars, automata theory
76
questions
49
votes
4
answers
12k
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).
...
- 1,286
21
votes
2
answers
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 ...
- 10.9k
9
votes
1
answer
794
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 ...
- 223
256
votes
11
answers
99k
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 ...
- 5,165
38
votes
12
answers
29k
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.
50
votes
5
answers
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 ...
- 1,249
30
votes
5
answers
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 ...
- 1,493
15
votes
1
answer
441
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 ...
- 14.1k
19
votes
1
answer
3k
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,...
- 1,386
40
votes
14
answers
27k
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 ...
- 559
40
votes
6
answers
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 ...
- 639
19
votes
3
answers
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'...
12
votes
3
answers
470
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^*\}$?
- 13.6k
20
votes
1
answer
2k
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 ...
- 13.6k
16
votes
2
answers
989
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 ...
- 263
16
votes
2
answers
752
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{...
- 21.3k
14
votes
1
answer
3k
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 ...
- 907
-2
votes
1
answer
528
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'...
- 131
25
votes
6
answers
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" ...
- 2,724
19
votes
6
answers
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 ...
- 677
29
votes
2
answers
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,...
- 10.1k
29
votes
2
answers
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 ...
- 749
26
votes
5
answers
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, ...
- 1,901
23
votes
1
answer
844
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 ...
- 7,485
22
votes
4
answers
4k
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 ...
- 323
20
votes
5
answers
802
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 ...
- 2,724
10
votes
5
answers
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 ...
- 935
31
votes
2
answers
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 ...
- 813
26
votes
2
answers
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 ...
- 363
9
votes
8
answers
7k
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?
- 131
17
votes
2
answers
710
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 ...
- 9,378
16
votes
1
answer
378
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 ...
- 3,916
14
votes
4
answers
609
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 ...
- 411
3
votes
0
answers
364
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 ...
- 443
31
votes
1
answer
820
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 ...
- 761
30
votes
4
answers
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 ...
- 31.8k
22
votes
2
answers
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 ...
- 5,444
21
votes
2
answers
7k
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 ...
- 321
14
votes
1
answer
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 ...
- 1,249
14
votes
3
answers
959
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 ...
- 143
13
votes
1
answer
295
views
Is { ww' | HamDist(w,w')>1 } context-free?
After reading the recent question "Is the complement of $\{ www \mid ...\}$ context-free?"; I remembered a similar problem I wasn't able to disprove:
Is $L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|...
- 22.3k
6
votes
7
answers
2k
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 ...
- 263
13
votes
0
answers
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 ...
- 231
12
votes
0
answers
324
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 ...
- 4,503
8
votes
1
answer
390
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 ...
- 13.6k
19
votes
1
answer
896
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$], ...
- 18.8k
12
votes
2
answers
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$ ...
- 712
12
votes
3
answers
430
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, ...
- 3,916
10
votes
3
answers
907
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 ...
- 907
9
votes
0
answers
360
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)\}$ ...
- 1,251