Questions tagged [context-free]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
31
votes
1answer
728 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 ...
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$ ...
23
votes
10answers
2k views

For a language to be programmable, is it mandatory that it be based on a context free grammar

Practically, for a language that can eventually be compiled/transformed into system level instructions, is it necessary that it be a context free grammar? ex: Are all programming/scripting languages ...
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(...
21
votes
2answers
2k views

Languages that we cannot (dis)prove to be Context-Free

I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques. Is there a recent survey on the subject or an open problem ...
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
708 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
588 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
1answer
7k views

How is proving a context free language to be ambiguous undecidable?

I've read somewhere that a Turing machine cannot compute this and it's therefore undecidable but why? Why is it computationally impossible for a machine to generate the parse tree's and make a ...
19
votes
1answer
743 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
662 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 ...
17
votes
2answers
262 views

A reference for a “more algebraic” approach to pushdown automata and CFLs?

In the Sakarovitch's book on automata theory, it is written in the introduction to the section on rationals in the free group that the material presented therein lays "the foundation of a truly ...
16
votes
1answer
628 views

Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?

In the formal description of Deterministic Pushdown Automata, they allow $\epsilon$ moves, where the machine can pop or push symbols onto the stack without reading a symbol from the input. If these $\...
16
votes
1answer
399 views

Are there variants of visibly pushdown automata that allow pushing of words onto the stack?

I'm wondering, are there any papers or research dealing with visibly pushdown automata, but allowing words, rather than single letters, to be pushed onto the stack. Alternately, a construction which ...
16
votes
1answer
170 views

Characterization of $L$ for which $\{ww : w \in L\}$ is not a CFL?

It is a standard proof in automata courses that for $L = \Sigma^\star$ and $|\Sigma| \ge 2$ that $S(L) = \{ww : w \in L\}$ is not a context-free language. It is also true that for any finite $L$, $S(...
16
votes
2answers
1k views

Permutation phrases with LR parsing

A permutation phrase is an extension to the standard (E)BNF context free grammar definitions: a permutation phrase $\{ A_1, \dots, A_n \}$ contains $n$ productions (or equivalently, nonterminals) $A_1$...
14
votes
1answer
1k views

Sufficient conditions for the regularity of a context-free language

It would be nice to collect a list of conditions that imply that a context-free language L is regular, i.e. conditions of the form: "if a given CFG/PDA has property P, then its languages is regular" ...
14
votes
1answer
363 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 ...
13
votes
1answer
241 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|...
12
votes
3answers
395 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^*\}$?
12
votes
3answers
336 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
754 views

Is SAT a context-free language?

I am considering the language of all satisfiable propositional logic formulae, SAT (to ensure that this has a finite alphabet, we would encode propositional letters in some suitable way [edit: the ...
12
votes
2answers
268 views

Reference for Dyck languages being $\mathsf{TC}_0$-complete

Dyck languages $\mathsf{Dyck}(k)$ is defined by the following grammar $$ S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon $$ over the set of symbols $\{(_1,\ldots,(_k,)_1,\...
11
votes
3answers
8k views

Ambiguity in regular and context-free languages

I understand the following claims to be true: Two distinct derivations of a string in a given CFG may sometimes attribute the same parse tree to the string. When there are derivations of some string ...
11
votes
2answers
266 views

On $n$ dimensional manifolds and lattices

EDIT (By Tara B): I'd still be interested in a reference to a proof of this, as I had to prove it myself for my own paper. I'm looking for the proof of Theorem 4 that appears in this paper: An ...
11
votes
0answers
104 views

Chomsky-Schützenberger for Deterministic CFLs

Is there a Chomsky-Schützenberger representation theorem for deterministic CFLs? Knowing precisely the class of morphisms under which DCFL is closed, such a theorem would probably be of the form: $...
11
votes
0answers
3k views

Eliminate ambiguity from CFG

CFG here stands for context-free grammar. I understand that: Deciding whether a CFG $G$ is ambiguous is undecidable. Deciding whether a CFL $L$ is inherently ambiguous is undecidable. My question ...
10
votes
1answer
689 views

Closure of unambiguous context-free languages under pre- and postfix.

Let $L$ be a context-free language. Define $ppc(L)$ to be the pre- and postfix closure of $L$, in other words, $ppc(L)$ contains all of $L$'s prefixes and postfixes, and hence $L$ itself. My question: ...
10
votes
1answer
273 views

What is the state complexity of the copy language?

Let a number $n$ be given. Consider the following language $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$. In words, $L_n$ is the set of copy strings of length $2n$. Consider the following ...
9
votes
2answers
8k views

Why is non-determinism (Push-down automata) necessary?

I would like to know why for the recognition of context-free languages only non-deterministic push-down automata (DPA=NPDA) work. Why do deterministic push-down automata (DPDA) not recognize such ...
9
votes
3answers
395 views

Continuous mathematics and formal language theory

Whether there are some results on solving formal languages problems using mathematical analysis, continuous mathematics. For example, solving the intersection non-emptiness problem for a context-free ...
9
votes
1answer
674 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 ...
9
votes
1answer
267 views

Membership problem for certain class of unrestricted grammars

Consider an arbitrary context-free grammar $G$ over the alphabet $\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$. To the productions of this grammar, add two fixed non-context-free productions $P$: $...
9
votes
1answer
170 views

Asymptotic density of ambiguous context-free grammars (CFGs)

What is the ratio of ambiguous CFGs to all CFGs? Since both sets are countably infinite the ratio is not well-defined. But what about the asymptotic density: $$\lim_{n \mapsto \infty}\frac {\# \...
9
votes
0answers
227 views

Complexity of a problem over acyclic context-free grammars

Let $G$ be an acyclic, context-free grammar over a fixed alphabet $\Sigma=\{a_1,\dots,a_k\}$ with the restriction (without loss of generality) that $|w|=2$ for each rule $A\to w$ in the grammar. ...
9
votes
0answers
322 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)\}$ ...
8
votes
1answer
2k views

Non-CFL closure properties

I was asked the following by a student, and couldn't come up with a complete answer: Are there any closure properties for the class of languages that are not context free? It's fairly easy to find ...
8
votes
1answer
197 views

Rational Functions and CFL

In my work arose the problem of classification CFL under rational functions images. In other terms, what class of languages form languages $T(L)$ , for fixed context free language $L$ and ...
8
votes
0answers
96 views

Does ${\bf CFLPAD}={\bf PPAD}$?

What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a (non-)deterministic finite/push-down automaton encodes the problem? I asked a similar ...
8
votes
0answers
1k views

Is there an ambiguity test for CFGs faster than trying all strings?

It is well known that testing whether a grammar is ambiguous is undecidable. It is however trivially decidable for any $G$ whether $L_n(G) := \{ w | w \in L(G) \wedge |w| \leq n \}$ for any $n \in \...
7
votes
2answers
243 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 ...
6
votes
2answers
221 views

Known and described subclasses of Context-Free Grammars class

I'm looking for various researches which consider specific subclasses of Context-Free Grammar class, i.e. some specific described cases, which differ from well-known: deterministic/non-deterministic ...
6
votes
1answer
259 views

Size of complement of context-free language

Let $L$ be a context-free language, $\bar L$ be its complement and $\bar L_n$ be the length $n$ words in $\bar L_n$. What is known about $|\bar L_n|$? Note that it is known that $|L_n|$ is either ...
6
votes
2answers
156 views

Are deterministic context-free languages closed under outfix (or other erasing operations)

Define the outfix of a language $L$ to be $Outf(L) = \{xy \mid \exists z. xzy \in L \}$. Are any known results about whether deterministic context-free languages are closed under this operation, or ...
6
votes
1answer
497 views

What is known about $CFL \cap coCFL$?

CFL is the class of context-free languages; co-CFL the languages whose complements are context-free. So CFL $\neq$ co-CFL. Are there any nice characterizations or other basic facts about CFL $\cap$ ...
6
votes
2answers
234 views

Investigation of Symbol Minimal Context-Free Grammars for the Language $a^n$

Question Given the language $L_n = \{ a^n \}$ for a natural number $n \geq 2$. Is there a symbol minimal context-free grammar $G$ that generates $L_n$ and contains a rule of the form $A \rightarrow ...
6
votes
1answer
122 views

Is this generalization of context free grammars known and strict?

Let $\Sigma$ be an finite alphabet and $(N, \circ)$ a semigroup. The semigroup operation on $N$ can be extended to $\mathscr{P}(N)$: $N_1 \circ N_2 := \{ \; n_1 \circ n_2 \; | \; n_1 \in N_1, \; n_2 \...
6
votes
2answers
223 views

Finding smallest context free grammar that generates a set of sets

Are there any results known about the size of smallest context free grammar that generates a set of sets? That is, I am given an alphabet $\Sigma$ as well as a set $S \subseteq \mathbb{P}(\Sigma)$ ...