# Questions tagged [context-free]

Context-free languages and grammars.

119 questions
Filter by
Sorted by
Tagged with
34 views

### Are there approaches to deriving a Grammar(production rules) from given set of strings?

Apologies for unambiguous question. So far I have a lot of difficulties of discerning on how to design formal production rules for some formal language aside from classic examples such as equal pairs ...
103 views

### Extensions of linear integer arithmetic decidable via Deterministic Pushdown Automata

I've recently learned about the connection between linear integer arithmetic (Presburger arithmetic) and Deterministic Finite Automata (DFAs). Namely, any formula in the first order theory of ...
1 vote
73 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 ...
• 163
155 views

• 151
290 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)$...
• 671
1 vote
146 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 ...
111 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,...
• 9,697
161 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 ...
• 434
233 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
86 views

• 23.1k
551 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
240 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 ...
• 14.1k
503 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^*\}$?
• 14.1k
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 ...
• 14.1k
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 ...
• 14.1k
177 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 ...
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 ...
• 14.1k
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 (...
1 vote
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-...
• 309
226 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 ...
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,157
### 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}$?