Questions tagged [context-free]

The tag has no usage guidance.

30 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
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 ...
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
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 \...
6
votes
0answers
436 views

Does PEG contain CFG?

Despite their considerable expressive power, all PEGs can be parsed in linear time using a tabular or memoizing parser (8). These properties strongly suggest that CFGs and PEGs define incomparable ...
6
votes
0answers
273 views

Language of stack configurations of a pushdown automaton

Consider a pushdown automaton $A$ with stack alphabet $\Gamma$. Let $L$ be the language on $\Gamma$ of the stack configurations encountered during accepting runs of $A$. Is $L$ a context-free language?...
5
votes
0answers
160 views

“Context” understanding in tree grammars

The Context-Free tree grammar has rules of the form: $A\rightarrow t$ or $A(x_1,\dots,x_n)\rightarrow t_x$, where $A\in N$, $t\in T(N\cup T)$, $t_x\in T(N\cup T\cup \{x_1,\dots,x_n\})$, $T(Z)$ ...
5
votes
0answers
135 views

Counting words of length $n$ in an inherently ambiguous CFG?

There is a polynomial-time algorithm for computing the number of words of length $n$ in an unambiguous CFG $G = (V, \Sigma, R, S)$ (via a dynamic programming approach). However, for ambiguous CFGs, ...
4
votes
0answers
663 views

Variant of a proof using Ogden's lemma

I am trying to understand better the proof that the language $K=\{a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} is not context-free. (see It only looks like a homework problem…), and the use of ...
4
votes
0answers
513 views

Minimal context-free Grammar for a special one-letter Language

For natural numbers $n \geq 5$, $m \geq 2^{n-2} + 1$ the following context-free language is given: $$ L_{n,m} = \{ a^i | 2 \leq i \leq m \} \setminus \{a^{2^i}|2 \leq i \leq n-2\} $$ Find and ...
4
votes
1answer
294 views

Is it known if $CFL \subseteq NSPACE(o(log^2(n)))$?

$CFL$ is the class of context-free languages. Question Is $CFL$ known to be solvable in $o(log^{2}(n))$ non-deterministic space? What about $DCFL$?
3
votes
0answers
167 views

Context-Sensitive Grammar characteristic properties

This question can look like some kind of puzzle, but it is actually part of more complex applied problem. Let's consider subspace of Context-Sensitive Grammars, which contains grammars which can not ...
3
votes
1answer
80 views

Reducing the Height of Context-Free Grammars

Let $G$ be a context free grammar in Chomsky normal form (CNF) with language $L(G)\subseteq \Sigma^n$. In other words, all strings generate by $G$ have size $n$. Say that a string $w\in L(G)$ has ...
2
votes
0answers
40 views

A Context-Sensitive Grammar which cannot be recognised by a Parsing Expression Grammar

It is (currently) an open question of whether every context-free grammar can be recognised by some parsing expression grammar. [1] However, has it been proven that there exists an example of a ...
2
votes
0answers
104 views

Is scalable hardware support for LogCFL (= sAC^1) possible?

The (uniform) circuit classes $TC^0$, $NC^1$ and $sAC^1$ seem to lend themselves to efficient hardware implementation. But using an FPGA approach to create the circuits on the fly seems problematic, ...
2
votes
0answers
485 views

Decidability of CFG ambiguity

I have been trying to show the following language is undecidable. $L = \{ (\langle G \rangle , n ): G$ is a context-free grammar with an ambiguous string of length $\le n \}$. I think it is ...
2
votes
0answers
254 views

Non-uniform CFG ambiguity decidability

The uniform version (the version which we normally see) of deciding whether a CFG (Context Free Grammar) is ambiguous is undecidable. But here I'd like to know something about the non-uniform version ...
2
votes
0answers
227 views

Structural equivalence of two context-free grammars

I understand that determining if two context-free grammars are structurally equivalent is decidable (according to the 1968 paper by Paull, M.C. and Unger, S.H., "Structural equivalence of context-free ...
1
vote
0answers
66 views

Sentences in what kinds of grammar in the Chomsky hierarchy can be parsed by an LSTM of a given size?

Given an LSTM $N$ of a given size $A$, a sentence $S$ with a given number of words $B$, a Chomsky grammar hierarchy level $C$ in 0-3, a Chomsky grammar $G$ of level $C$ of size $D$, A given fixed, ...
1
vote
0answers
26 views

Is there an unambiguous grammar that has no left recursion or left factors, but is not in $LL(1)$?

I know that, for a grammar $G$ to belong to $LL(1)$, it is necessary that $G$ is not ambiguous; that is, every sentence has a unique parse tree in $G$. $G$ has no left recursion; that is, we can't ...
1
vote
0answers
52 views

What is the interpretation of an infinite formal context-free grammar?

Let $L$ be a language as follows: $$ \begin{align*} L &::= a\ |\ L^{*}\\ \end{align*} $$ Now, suppose I apply some sort of transformation $T : N \rightarrow N$ where $N$ is the set of non-...
1
vote
0answers
85 views

Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form?

Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form? I cannot find an reference.
0
votes
0answers
24 views

Difference between 'string relations' and 'tree relations' w.r.t. synchronous CFGs

Context: http://www3.nd.edu/~dchiang/papers/synchtut.pdf On page 3, under the section Properties, at the end of the paragraph labeled Closure under composition?, the author mentions 'tree relations ...
0
votes
0answers
131 views

CSP-problem, based on context-free grammar

I'm trying to solve a CSP (Constraint-Satisfaction-Problem), which is based on arbitrary context-free grammars. A quick example: Let's say we have a context-free grammar with the following production ...
0
votes
0answers
157 views

In what complexity classes other than $NP$ are these problems related to unary languages?

If I remember correctly saw this reduction in a paper can't find at the moment. Consider the following NP-complete variation of the Subset Sum problem. Given a set of positive integers $S=\{x_1,\...