Questions tagged [context-free]
Context-free languages and grammars.
114
questions
0
votes
0
answers
135
views
The difference between the 1st and 2nd editions. "Compilers Principles, Techniques, and Tools" by Aho, Sethi and Ullman
I bought "Compilers Principles, Techniques, and Tools 1st Edition" by Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman long years ago and it has been sitting on my bookshelf ever since.
I ...
- 101
4
votes
1
answer
183
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....
- 303
0
votes
0
answers
62
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 ...
3
votes
0
answers
70
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 ...
- 303
4
votes
0
answers
71
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 ...
- 279
3
votes
0
answers
103
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.
...
- 4,475
6
votes
0
answers
252
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 ...
- 59
10
votes
0
answers
248
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 ...
- 3,946
1
vote
1
answer
53
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 ...
5
votes
1
answer
168
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 $\...
- 151
9
votes
1
answer
260
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)$...
- 661
1
vote
1
answer
136
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 ...
- 11
9
votes
0
answers
106
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,...
- 8,896
2
votes
1
answer
152
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 ...
- 424
6
votes
1
answer
215
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 ...
- 59
1
vote
0
answers
84
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 $\...
- 61
0
votes
1
answer
136
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?
- 11
2
votes
0
answers
100
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 ...
- 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 ...
- 411
5
votes
1
answer
102
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 ...
- 411
7
votes
0
answers
106
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, ...
- 917
3
votes
1
answer
178
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 ...
- 917
3
votes
0
answers
146
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 ...
- 131
7
votes
1
answer
138
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 ...
- 22.6k
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 ...
- 917
6
votes
1
answer
614
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 ...
- 103
5
votes
1
answer
194
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 ...
- 13.9k
1
vote
0
answers
74
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, ...
- 107
2
votes
0
answers
69
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 ...
- 121
21
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 ...
- 22.6k
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 ...
- 11.4k
1
vote
0
answers
78
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 ...
- 81
13
votes
1
answer
305
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|...
- 22.6k
9
votes
3
answers
535
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 ...
- 91
5
votes
1
answer
231
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 ...
- 13.9k
12
votes
3
answers
490
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^*\}$?
- 13.9k
6
votes
1
answer
296
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 ...
- 13.9k
8
votes
0
answers
102
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 ...
- 13.9k
4
votes
2
answers
152
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 ...
- 175
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 ...
- 13.9k
6
votes
1
answer
165
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 (...
- 635
1
vote
0
answers
65
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-...
- 309
5
votes
2
answers
208
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 ...
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 ...
- 5,127
9
votes
1
answer
838
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}$?
- 5,127
7
votes
1
answer
168
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 \...
- 59
5
votes
0
answers
163
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)$ ...
- 635
6
votes
1
answer
2k
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 ...
- 395
2
votes
0
answers
121
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, ...
- 3,033
2
votes
1
answer
231
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 $\...
- 31