Questions tagged [context-free]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6
votes
1answer
170 views

Context Free Grammar For Complement Of { www | … } with minimal pumping length?

Let $L := \{ w^3 | w \in \{0,1\}\}^C$ be the complement of the language of words that are not the 3rd power of a word over $\Sigma = \{0,1\}$. Let's define the largest minimal pumping length of a ...
1
vote
0answers
77 views

Take a natural quotient of context-free grammars

Fix a finite alphabet. Let $\mathrm{CFG}$ be the set of context-free grammars on this alphabet, $\mathrm{CFL}$ the set of context-free languages, $\mathrm{UG}$ the set of unrestricted grammars and $\...
0
votes
1answer
86 views

Reference for context-free grammar for Martin-Löf type theory

Are the terms and the types of Martin-Löf type theory described by context-free grammars? Have such grammars been written down somewhere?
2
votes
0answers
67 views

Necessary and sufficient condition for an infinite tree to be context-free

A Buchi automaton is non-empty iff it accepts an infinite word of the form $uv^\omega$ (here $u,v$ are finite words). In other words, if $\{w\}$ is an $\omega$-regular language, then it is of that ...
5
votes
1answer
125 views

Different definitions of grammar complexity

It's known that there are different "kinds" of grammar complexity of language $L$ --- nonterminal complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L$), covering ...
5
votes
1answer
88 views

Nonterminal descriptional complexity of regular languages

Recently I became interested in grammar complexity of regular language. Prior to searching for literature, I tried to investigate it on my own, proving two lemmas from comment below. I am aware of an ...
7
votes
0answers
99 views

Deciding whether DCFG is visibly pushdown

Is the following problem decidable? If so, what's the best algorithm known? Instance: a deterministic pushdown automaton $A$ Question: Does there exist (i) some partition of the alphabet into push, ...
3
votes
1answer
113 views

Generalizations of Dyck languages?

The "narrowest" generalization of Dyck languages that I am aware of is Visibly Pushdown languages. Are there any useful classes of languages that are intermediate between Dyck languages and ...
3
votes
0answers
71 views

Deciding whether an arbitrary context-free grammar generates a deterministic push-down automata?

I know that it's undecidable whether an arbitrary context-free grammar is ambiguous, but is it decidable whether that grammar is deterministic? I can't find the answer to this question anywhere on the ...
7
votes
1answer
119 views

Lengths of “all-accepted” words in Context Free languages

If $L$ is a Context Free language, it can happen that for some $n$, all words of length $n$ are in $L$. If we consider the set $A_L$ of such lengths represented in unary, we may guess that such set is ...
10
votes
3answers
725 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 ...
4
votes
1answer
330 views

Are endmarkers necessary for Deterministic Pushdown Automata?

In the book by Kozen (Automata and Computability), the transition function of deterministic pushdown automata (DPDAs) is supposed, in contrast with non-deterministic pushdown automata (NPDAs), to ...
5
votes
1answer
141 views

Are PDAs without ϵ moves and with bounded stack operation as powerful as PDAs with them?

It is known that PDAs without $\epsilon$ moves are as powerful as PDAs with them. However, it seems to me that the proof allows several stack operations in one move. What happens if we allow at most ...
1
vote
0answers
70 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, ...
2
votes
0answers
54 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 ...
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 ...
3
votes
1answer
139 views

Compressing grammars by introducing ambiguity and left-recursion

This is a reference request. What is known about the following questions? Problem: Given a grammar $G$ (for example context-free) with language $L$ we can introduce a new grammar $G'$ which also ...
1
vote
0answers
46 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 ...
13
votes
1answer
272 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|...
9
votes
3answers
452 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
186 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 ...
12
votes
3answers
450 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
272 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
100 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
97 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
154 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
58 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-...
5
votes
2answers
166 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 ...
5
votes
1answer
992 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 ...
5
votes
1answer
427 views

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

$\mathrm{CFL}$ is the class of context-free languages. Question Is $\mathrm{CFL}$ known to be solvable in $o(log^{2}(n))$ non-deterministic space? What about $\mathrm{DCFL}$?
6
votes
1answer
134 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
161 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)$ ...
6
votes
1answer
1k 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
106 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
226 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
973 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
661 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
139 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\...
3
votes
1answer
234 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
1k 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
278 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
222 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
168 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
298 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)$ ...
6
votes
2answers
258 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
0answers
645 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 ...
-8
votes
1answer
89 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 ...
3
votes
2answers
256 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
400 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, ...