Questions tagged [fl.formal-languages]

formal languages, grammars, automata theory

Filter by
Sorted by
Tagged with
251
votes
11answers
96k 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 ...
46
votes
5answers
6k 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
15k 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
5k 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
24k 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
26k 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
760 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
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
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 ...
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,...
27
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 ...
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
671 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
505 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
666 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, ...
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
3answers
738 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
0answers
620 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
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 ...
19
votes
5answers
682 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
439 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
881 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
674 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
613 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
784 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
289 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
440 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
911 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
577 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
763 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 ...

1
2 3 4 5
8