Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [context-free]

Context-free languages and grammars.

Filter by
Sorted by
Tagged with
-2 votes
0 answers
24 views

What is the use of endmark symbol in DPDA?

I am stuck with the idea of endmark symbol in dpda and its Theorem 2.43. A is a DCFL if and only if A⊣ is DCFL in Michael Sipser's Introduction to the Theory of Computation. Can anybody explain with ...
charan k's user avatar
-2 votes
0 answers
45 views

Is the grammar for fully specified json ambiguous?

There are some examples (like python's lark) parsing a json grammar using lalr parser. Is he a subset of json? My gut tells me full json must be parsed by a parser that must handle ambiguity...but I ...
user947659's user avatar
1 vote
0 answers
57 views

Not possible to write deterministic CFG for balanced parenthesis?

I know that it's possible to build an LL(1) parser for the Dyck language, i.e. a balanced string of parentheses, so the Dyck language is a deterministic context-free language. But what's an example of ...
Jerry Ding's user avatar
5 votes
2 answers
147 views

Modify DCFG to enforce length limit

Given a deterministic context-free grammar $G$ that generates the language $L$, is there an efficient algorithm that can be used to construct another DCFG $G_N$ that generates the language $\{ s \in L ...
Jerry Ding's user avatar
13 votes
4 answers
967 views

List of nice non-context-free languages

I am trying to separate classes of formal languages from each other. One of these classes is the class of context-free languages. To this end, it would be handy to have a list of languages which are ...
NerdOnTour's user avatar
2 votes
0 answers
40 views

Characterization of CF languages closed under circular shifts

Along the same lines as what was asked in this post: Is there a simple characterization of regular languages closed under circular shifts? Are there simple characterizations/properties of Context Free ...
Marzio De Biasi's user avatar
4 votes
1 answer
197 views

Pumping lemma for CFL intersection

The class of context-free languages is not closed under intersection. For example, the language $L=\{a^nb^nc^n : n\geq 0\}$ is not context-free, but it is an intersection of two context-free languages....
QMath's user avatar
  • 303
0 votes
0 answers
73 views

Are there data structures that cannot be serialized / deserialized using a context free grammar?

I understand that deserializing data from a string or binary stream into a data structure is effectively the same parsing. When you deserialize the input string, you use a grammar to create a parse ...
bcarlborg's user avatar
3 votes
0 answers
73 views

Time complexity of context-free languages

I am reading an old paper [1] about time complexity of context-free languages. The computational model is the standard one-tape Turing machine. It is written on page 377 without a proof that "we ...
QMath's user avatar
  • 303
5 votes
0 answers
80 views

Equivalent Characterizations of Semilinear Sets

Coming from an automata theory background, the semilinear sets seem like an ideal candidate for having lots of equivalent characterizations. I am already familiar with a few well known ones: Sets ...
TomKern's user avatar
  • 489
3 votes
0 answers
108 views

Context-free languages and free/bound variables

Fix a first-order language $L_0$, and let $$L=\{f(\varphi)\mid \varphi \text{ is a well-formed formula of $L_0$}\},$$ where $f(\varphi)$ is $\varphi$ with all occurrences of free variables underlined. ...
Bjørn Kjos-Hanssen's user avatar
6 votes
0 answers
257 views

Context Free Grammar For Complement Of { wwwww | ... } With Minimal Locality?

Definitions Let $G$ be a context free grammar over an alphabet $\Sigma$ with non-terminals $V$. Define the locality $l(G)$ as the length of the longest word in $(V \cup \Sigma)^*$ that has a ...
Henning's user avatar
  • 59
10 votes
0 answers
250 views

Smallest context-free grammar for powers of two summing to $2^k$

Let $k > 0$ and define an alphabet $\Sigma_k = \{ 2^0, 2^1, \ldots, 2^k \}$. Define: $$P_k = \{ a_1a_2\cdots a_t \in \Sigma_k^* \mid \sum_i a_i = 2^k \}.$$ This is a finite language. Question: Is ...
Michaël Cadilhac's user avatar
1 vote
1 answer
57 views

CFG - How can I describe a language that dictates a word and its opposite?

I have this question from my Automata class and I am unsure if there's a way to do this. Assuming u,v ∈ {0,1}* and at every character in the word u, the character at the same position in the word v is ...
alyelalwany's user avatar
5 votes
1 answer
173 views

Establishing competing memory limits for pushdown automata

Let $L$ be the language of all even-length strings whose first half is a palindrome. Let $L$ be the language of all even length strings whose first half is imbalanced—with an unequal number of $\...
user326210's user avatar
9 votes
1 answer
279 views

Words of the form $(a^n b)^n$ in a context-free language

Question For a language $L \subset \{a,b\}^*$, denote $N(L) = \{ n \geq 0 \mid (a^n b)^n \in L \}$. If $L$ is context-free, is $N(L)$ necessarily semilinear, meaning that $n \in N(L) \iff n+p \in N(L)$...
Ilkka Törmä's user avatar
1 vote
1 answer
141 views

Bounded non-emptiness intersection of deterministic context-free grammars

Let A and B be two determinstic context-free grammar, and let N be an integer: What's the complexity of deciding if the intersection of the languages accepted by A and B over all strings of length ...
RockyBilboa's user avatar
9 votes
0 answers
110 views

Expressiveness of pushdown automata whose stack height sequence is unambiguous

I consider pushdown automata on an alphabet $\Sigma$, which are intuitively finite automata with a stack. Formally, a pushdown automaton $A = (Q, q_0, F, \Gamma, \Delta)$ is a finite set $Q$ of states,...
a3nm's user avatar
  • 9,419
2 votes
1 answer
155 views

Does a finite, polynomially-bounded CFG translate into a polynomially-bounded DFA?

We are given a family of context-free grammars $\{ G_1, G_2, G_3, ..., G_n, ...\}$ where each $G_n$ generates strings only of length $n$ and obeys other constraints specified below. We want to study ...
ShyPerson's user avatar
  • 434
6 votes
1 answer
228 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 ...
Henning's user avatar
  • 59
1 vote
0 answers
86 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 $\...
naloa's user avatar
  • 61
0 votes
1 answer
146 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?
neinoa's user avatar
  • 11
2 votes
0 answers
103 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 ...
Faustus's user avatar
  • 193
5 votes
1 answer
145 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 ...
DG_'s user avatar
  • 411
5 votes
1 answer
105 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 ...
DG_'s user avatar
  • 411
7 votes
0 answers
111 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, ...
Antimony's user avatar
  • 917
3 votes
1 answer
187 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 ...
Antimony's user avatar
  • 917
3 votes
0 answers
155 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 ...
Joshua Wise's user avatar
7 votes
1 answer
143 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 ...
Marzio De Biasi's user avatar
11 votes
3 answers
1k 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 ...
Antimony's user avatar
  • 917
6 votes
1 answer
674 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 ...
user251130's user avatar
5 votes
1 answer
210 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 ...
domotorp's user avatar
  • 14k
1 vote
0 answers
75 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, ...
Lars Ericson's user avatar
2 votes
0 answers
72 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 ...
Alex W's user avatar
  • 121
22 votes
2 answers
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 ...
Marzio De Biasi's user avatar
3 votes
1 answer
166 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 ...
Martin Berger's user avatar
1 vote
0 answers
80 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 ...
Berserker's user avatar
13 votes
1 answer
309 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|...
Marzio De Biasi's user avatar
9 votes
3 answers
546 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 ...
Rustam's user avatar
  • 91
5 votes
1 answer
238 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 ...
domotorp's user avatar
  • 14k
12 votes
3 answers
500 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^*\}$?
domotorp's user avatar
  • 14k
6 votes
1 answer
298 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 ...
domotorp's user avatar
  • 14k
8 votes
0 answers
103 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 ...
domotorp's user avatar
  • 14k
4 votes
2 answers
171 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 ...
Rahul Gopinath's user avatar
21 votes
1 answer
2k 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 ...
domotorp's user avatar
  • 14k
6 votes
1 answer
167 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 (...
Andrey Lebedev's user avatar
1 vote
0 answers
67 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-...
CinchBlue's user avatar
  • 309
5 votes
2 answers
217 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 ...
Mateus de Oliveira Oliveira's user avatar
6 votes
1 answer
2k 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 ...
Michael Wehar's user avatar
9 votes
1 answer
872 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}$?
Michael Wehar's user avatar