# Tag Info

### Is there a one-state PDA that recognizes every context free language?

We have to be precise. Each context-free language can be accepted by empty stack using a push-down automaton with a single state, or by final state and two states. (In the latter case we obviously ...
• 30.8k
Accepted

### Subset Relations Between CFGs and Their Languages

Let $G$ and $H$ be your two context-free grammars, respectively. If the set of all rules in $G$ is a subset of the set of all rules in $H$, then all derivations possible in $G$ are also possible in $H$...

### Is the complement of this context-free language also context-free?

Here's a somewhat simple, non-constructive approach. Try to convince yourself, that $\mathcal{G}$ generates a deterministic context-free language. Since all deterministic context-free languages are ...
• 1,467
Accepted

### Repeated rules with more than three symbols for conversion to Chomskys Normal Form

Yes, if the same strings are generated the productions can be shared. The "standard" conversion does not consider such "coincidences". Note that your final result does not yet ...
• 30.8k

### Proving that the scramble of a regular language is context-free

We can prove this without using Parikh's theorem. Assume that a language $L$ over the two-letter alphabet $\{0,1\}$ is given by a finite-state machine. For the language $\mathrm{SCRAMBLE}(L)$ we ...
• 198

• 163k
Accepted

### Is the complement of this context-free language also context-free?

Summary The above context free grammar $\mathcal{G}$ has an equivalent pushdown automation $M$. As the starting letters of $u$ and $v$ are different ($a$ and $b$), we can create a $M$ which is a ...
• 664
Accepted

### What is the name of the diagram used in JSON spec for representing a context-free language?

It's called a "syntax diagram", "syntax chart", or "railroad diagram". Of these three, "syntax diagram" is the most common term. They're sometimes called "...
• 22.6k
Accepted

### How it possible given string belong to given grammar

This is possible, provided there is a solution in nonnegative integers to the following pair of equations.  \left\{ \begin{array}{rcrc@{\qquad}l} x & + & 2y & = & 2020 \\ ...
• 30.8k
Accepted

• 1,467

### Does the pumping lemma for context-free languages really require accepting a string with zero levels of nesting?

If the string generated by the grammar is long enough then somewhere in the derivation tree we will find a path with a repeated variable. Below that is $A$. This induces the devision $vwxyz$ of the ...
• 30.8k
Accepted

• 198

### Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language

The language is context-free. Slightly different: Context free grammar construction $\{ a^mb^n \mid m≤n≤2m \}$. For strings where the symbols $a,b$ may be in any order, you might find inspiration in ...
• 30.8k
Accepted

### Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language

As the other answers indicate, the language is indeed context-free. Writing a grammar for it is a bit tricky, but we can do it as follows. $N_a(x) = N_b(x)$ First, let's consider the (much) simpler ...
• 713

### Is matching pairs sufficient?

I assume that the Turing machine $M$ is allowed to be nondeterministic. In that case we need three positions. Consider the possibility that $M$ on a certain configuration may move either left or right....
• 30.8k
Accepted

### Efficiently transforming non-recursive CFG into an NFA

Build a directed graph, with one vertex per non-terminal, and an edge $A \to B$ if there is a rule in the grammar where $A$ is on the left-hand side and $B$ appears on the right-hand side. Since you ...
• 163k
Accepted

### Question about a grammar who generates $(0+1)^*$

We can prove this using mathematical induction. For base case, it is easy to see that $S$ can generate $\varepsilon, 0, 1, 00, 11, 01, 10$. Now we assume $S$ can generate any binary string on $0$s and ...
• 1,860
Accepted

• 29.6k