342
I have personally enjoyed several Aha! moments from studying basic automata theory. NFAs and DFAs form a microcosm for theoretical computer science as a whole.
Does Non-determinism Lead to Efficiency? There are standard examples where the minimal deterministic automaton for a language is exponentially larger than a minimal non-deterministic automaton. ...
51
Ever used a tool like grep/awk/sed? Regular expressions form the heart of these tools.
You'll be surprised how much coding you can avoid by principled use of regular expressions - in "practical projects", like an email server.
If you're a CS major, you'll definitely be writing a compiler/interpreter for a (at least a small) language. If you've ever tried ...
43
To complete the other answers: I think that Turing Machine are a better abstraction of what computers do than finite automata.
Indeed, the main difference between the two models is that with finite automata, we expect to treat data that is bigger than the state space, and Turing Machine are a model for the other way around (state space >> data) by making the ...
37
For a DFA, in which the initial state is state $0$, the number of words of length $k$ that end up in state $i$ is $A^k[0,i]$, where $A$ is the transfer matrix of the DFA (a matrix in which the number in row $i$ and column $j$ is the number of different input symbols that cause a transition from state $i$ to state $j$). So you can count accepting words of ...
34
Yes, there is. Define a context-free expression to be a term generated
by the following grammar:
$$
\begin{array}{lcll}
g & ::= & \epsilon & \mbox{Empty string}\\
& | & c & \mbox{Character $c$ in alphabet $\Sigma$} \\
& | & g \cdot g & \mbox{Concatenation} \\
& | & \bot & \mbox{...
33
There are many good theoretical reasons to study N/DFAs. Two that immediately come to mind are:
Turing machines (we think) capture everything that's computable. However, we can ask: What parts of a Turing machine are "essential"? What happens when you limit a Turing machine in various ways? DFAs are a very severe and natural limitation (taking away ...
32
One of the more practical manifestation of CS is Compiler Construction. In 1965, Knuth started the study of LR parsers. Quickly (in less than a decade), we had LALR parsers which are a subset of deterministic pushdown automata that allows us to implement shift/reduce parsers.
At the heart of the feasibility and efficiency of LALR parsing is a proof (by ...
32
There are two approaches when considering this question: historical that pertains to how concepts were discovered and technical which explains why certain concepts were adopted and others abandoned or even forgotten.
Historically, the Turing Machine is perhaps the most intuitive model of several developed trying to answer the Entscheidungsproblem. This is ...
31
To add one more perspective to the rest of the answers: because you can actually do stuff with finite automata, in contrast with Turing machines.
Just about any interesting property of Turing machines are undecidable. On the contrary, with finite automata, just about everything is decidable. Language equality, inclusion, emptiness and universality are all ...
30
Can you hear that noise? It is the sound of a thousand brilliant theorems, applications and tools laughing in automata-theoretic heaven.
Languages and automata are elegant and robust concepts that you will find in every area of computer science. Languages are not dry, formalist hand-me-downs from computing prehistory. The language theory perspective ...
28
Neither!
The best way to see this independence is to read the original papers.
Turing's 1936 paper introducing Turing machines does not refer to any simpler type of (abstract) finite automaton.
McCulloch and Pitts' 1943 paper introducing "nerve-nets", the precursors of modern-day finite-state machines, proposed them as simplified models of neural activity, ...
27
State. you need to learn that one can model the world (for certain problems) as a finite state space, and one can think about computation in this settings. This is a simple insight but extremely useful if you do any programming - you would encounter state again and again and again, and FA give you a way to think about them. I consider this to be a sufficient ...
27
Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser:
Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$
Or there exists a $c>1$, so that $w_n\ge c^n$ for infinitely many $n$.
This has been shown for instance in:
Roberto Incitti:
"The growth function of context-free ...
25
I'm not quite sure which flavour of "why" you are looking for. One reason for the increase in power when allowing nondeterminism can be seen in the following example:
Let $L$ be the set of palindromes $w\bar{w}$ over some alphabet (of at least two symbols), where $\bar{w}$ is the reverse of $w$. An NPDA for this language can just keep pushing symbols onto ...
25
This is really a stubborn -- and well-studied -- problem. Regarding positive results, an exact algorithm by Kameda and Weiner, a heuristic approach by Polák, and a recent approach using SAT solvers by Geldenhuys et al. come to mind. But there seem to be far more negative results ruling out other possible approaches (e.g. approximation algorithms, special ...
23
Unambiguous context-free parsing is in $O(n^2)$ using Earley's algorithm. Whether there exists a parsing algorithm working in linear-time on all the unambiguous context-free grammars is an open problem. One of the most advanced statements of this kind is due to Leo [1991], who showed that a variant of Earley parsing works in linear time for all LRR ...
22
Practically speaking, what are examples of languages or grammars that regex can always parse successfully?
A short answer is: Probably nothing that you call a language.
In theoretical computer science (TCS), a language simply means a set of words. But in most cases, what people call a “language” outside TCS has some recursive structure. “Recursive ...
22
How about $L:=\{a^{n^2}\mid n\in\mathbb{N}\}$? It is easy to see that $L$ and its complement are not regular, and hence (as we are dealing with a unary alphabet) not context-free.
21
Although it is not really the reason they were originally studied, finite automata and the regular languages they recognize are tractable enough that they have been used as building blocks for more complicated mathematical theories. In this context see particularly automatic groups (groups in which the elements can be represented by strings in a regular ...
20
See Mike Domaratzki's paper, State complexity of proportional removals
http://dl.acm.org/citation.cfm?id=782471
http://www.cs.umanitoba.ca/~mdomarat/pubs/sc_jalc.ps
19
I think that this question has been studied previously. Mike Domaratzki wrote a survey on research in this area:
"Enumeration of Formal Languages", Bull. EATCS, vol. 89 (June 2006), 113-133: http://www.eatcs.org/images/bulletin/beatcs89.pdf
19
About Q1:
Both the ambiguity problem (given a CFG, whether it is ambiguous) and the inherent ambiguity problem (given a CFG, whether its language is inherently ambiguous, i.e. whether any equivalent CFG is ambiguous) are undecidable. Here are the original references:
The undecidability of ambiguity was proved by Cantor (1962), Floyd (1962), and Chomsky and ...
19
There is the notion of primality of a language. It asks whether L can be written as $L_1 \cdot L_2$ where neither factor contains the empty word. A language is prime if it cannot be written in this form.
For a given regular language, represented by a DFA, it is shown in [MNS] that it is PSPACE-complete to decide primality.
[MNS] Wim Martens, Matthias ...
18
There has been a lot done applying category theory to regular languages and automata. One starting point is the recent papers:
Bialgebraic Review of Deterministic Automata, Regular Expressions and Languages
by Bart Jacobs
A Bialgebraic Approach to Automata and Formal Language Theory by James Worthington.
In the first of these papers, the structure of ...
18
State complexity is really about concise description of an object (in this case, a regular language), not about computational complexity. The general topic is called "descriptional complexity" in the literature and draws its inspiration, in part, from the classic 1971 paper of Meyer and Fischer entitled "Economy of Expression by Automata, Grammars, and ...
18
You are asking (at least) two different questions: (a) What parts of theory build on finite automata nowadays? (b) Why were finite automata developed in the first place? I think the best way to address the latter is to look at the old papers, such as:
Rabin, Scott, Finite Automata and Their Decision Problems, 1959
Here are the first two paragraphs:
...
17
Let $A = (Q = \{q_1, \dots, q_n\}, \Sigma, \delta, Q_F)$ be a (nondeterministic) finite automation with starting state $q_1$, $Q_F \subseteq Q$ and $\delta \subseteq Q\times\Sigma\times Q$.
Let $Q_i(z)$ the generating function for all the words that can be accepted starting in $q_i$, that is the $n$th coefficient of its series expansion $[z^n]Q_i = |\{w \...
17
Two more constructions: Brzozowski-McCluskey aka state elimination [1], and Gaussian elimination in a system of equations using Arden's Lemma. The best source on these is probably Jacques Sakarovitch's book [2].
[1] J. Brzozowski, E. McCluskey Jr., Signal flow graph techniques for sequential circuit state diagrams, IEEE Transactions on Electronic
Computers ...
17
Lower bounds for algebraic circuits
In the setting of algebraic circuits, where a lower bound on circuit size is analogous to a lower bound on time, many results are known, but there are only a few core techniques in the more modern results. I know you asked for time lower bounds, but I think in many cases the hope is that the algebraic lower bounds will ...
16
I thought about this problem again, and I think I have a full proof. It is a bit more tricky than what I anticipated. Comments are very welcome! Update: I submitted this proof on arXiv, in case this is useful to someone: http://arxiv.org/abs/1207.2819
$\DeclareMathOperator{\fp}{fp}$
$\DeclareMathOperator{\lp}{lp}$
$\newcommand{\fpp}[1]{\widehat{\fp{#1}}}$
$\...
Only top voted, non community-wiki answers of a minimum length are eligible
