Questions tagged [context-free]
The context-free tag has no usage guidance.
11
votes
1answer
192 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|...
6
votes
2answers
172 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 ...
5
votes
1answer
129 views
For which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?
Unless I'm mistaken, a language of the form $\{0^a10^b\mid R(a,b)\}$ is context-free if and only if $R$ is a finite union of linear (in)equalities involving integer constants and the variables $a$ and ...
9
votes
1answer
152 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^*\}$?
6
votes
1answer
210 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 ...
8
votes
0answers
92 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 ...
4
votes
1answer
77 views
What is the current state of the art in black-box grammar induction?
Grammar induction of Context Free Languages seems to be a very well researched field. I would like to know the current state of the art in inducing a Context Free Grammar (I am reading up Higuera's ...
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 ...
6
votes
1answer
123 views
Example of context-free tree language which can not be generated by monadic CFTG
Assuming that a context-free tree language (CFTL) is that which is generated by a context-free tree grammar (CFTG), I am looking for an example of CFTL which can not be generated by a monadic CFTG (...
1
vote
0answers
45 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-...
3
votes
1answer
74 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 ...
4
votes
1answer
203 views
What is the complexity of counting parse trees?
A Counting Problem
Given a CFG $G$ and a string $s$, how many distinct parse trees are there for the string $s$?
An Example Instance
Let's consider an example instance consisting of a CFG $G$ with ...
4
votes
1answer
222 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$?
6
votes
1answer
115 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 \...
5
votes
0answers
158 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
1answer
303 views
Show that minimal CFG is undecidable via mapping reduction
Actually the problem below is an exercise in Sipser's textbook (Problem 5.36). However, from my perspective, it is not so trivial so that I post this question on this site instead of CS.SE.
The ...
2
votes
0answers
94 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
1answer
210 views
Deformation of finite regular languages [closed]
Let $L \subseteq \{0,1\}^n$ be any finite regular language s.t it has an acyclic DFA.
Let $C$ be some class of acyclic DFAs.
Let $\sigma \in S_n$ be a permutation on $n$ symbols. We can apply $\...
19
votes
1answer
531 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 ...
20
votes
0answers
526 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 ...
5
votes
1answer
131 views
Regarding proper form of production rules of Context-free tree grammars
Is it possible to describe Context-free Tree Grammar $G_t$ such that set of yields of its trees will coincide with Context-sensitive word language $a^nb^nc^n$?
$\{a^nb^nc^n | n>0\}=\{Yield(t)|t\...
4
votes
1answer
212 views
Compression algorithms for low-complexity strings?
Let $s$ denote a string over a finite alphabet, $n_s = |s|$ be the length of $s$, and $n_s^{*}$ denote the minimum description size of $s$ under a given computational model (TM, CFG, etc.). Are there ...
13
votes
2answers
639 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 ...
17
votes
2answers
229 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
152 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(...
3
votes
0answers
160 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 ...
6
votes
2answers
187 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)$ ...
7
votes
2answers
203 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
...
5
votes
0answers
328 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 ...
-9
votes
1answer
75 views
In what way are these two context free grammar equal? [closed]
Consider the grammar
G1: A->Aα|β
G2: A->βX
X->αX|ϵ
Its was said that these two grammars are equal.
Should something like left recursion be removed? In what sense are these equal? Am really ...
4
votes
2answers
154 views
Finding a minimal context free grammar that recognizes a finite set of strings of bounded length
Problem:
Given a finite set of strings $\{x_1, x_2, ..., x_n\}$ of length $\ell$ or less from some finite alphabet $\Sigma=\{a_1, a_2, ..., a_k\}$, find the minimal context free grammar that ...
12
votes
3answers
292 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, ...
9
votes
0answers
219 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. ...
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 ...
5
votes
0answers
123 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, ...
-1
votes
1answer
136 views
Can context-free grammar generates $a^{2^n}$ [closed]
Context-free grammar can generate the string $a^{2^n}$ for $n \geq 0$.
The production rule P is $S \rightarrow SS | a$.
The derivations is, for example:
1) $S \Rightarrow a$ (this is when n = 0)
2)...
10
votes
0answers
94 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:
$...
15
votes
1answer
455 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 $\...
0
votes
2answers
165 views
Example of R and G when $R \subseteq L(G)$ is undecidable [closed]
Could anybody provide an example of regular language R and context-free grammar G such that $R \subseteq L(G)$ is undecidable. Of course, if such language could be constructed.
Thanks.
10
votes
1answer
262 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 ...
0
votes
0answers
128 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 ...
2
votes
1answer
2k views
Deciding whether a context-free language is regular [closed]
Does anyone know whether the following decision problem is decidable:
Given a context-free language $L$, is $L$ regular?
Here $L$ can be expressed, e.g., using a context-free grammar. Does anyone ...
2
votes
0answers
351 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 ...
9
votes
1answer
251 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$: $...
0
votes
0answers
150 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,\...
4
votes
1answer
246 views
What characterizations exist for the grammars that can express subsets of the context-free languages?
It is well known that CFGs and PDAs are equivalent, and there has been extensive research about the relationship between deterministic pushdowns and $LR(1)$ grammars, as $DCFL$ is a subset of $LR(1)$.
...
6
votes
2answers
142 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 ...
20
votes
3answers
635 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$?
9
votes
1answer
165 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
{\# \...
1
vote
0answers
84 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.
