16 votes
Accepted

Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form

Sipser clearly implies an or between those two rules. The two definitions say the same thing. Meanwhile, in formal language theory, it is quite common for two textbooks or article to not say the same ...
reinierpost's user avatar
  • 5,519
8 votes

Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form

Sipser doesn't require that both of those forms be used. It just requires that every rule fit one of those two patterns.
D.W.'s user avatar
  • 159k
6 votes

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 ...
Hendrik Jan's user avatar
  • 30.6k
5 votes
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 ...
Hendrik Jan's user avatar
  • 30.6k
5 votes

Does there exist an context free language L such that L∩L^R is not context free?

Consider $L = \{ a^n b^n a^m \mid m,n\ge 1\}$. In fact you can repeat this to get more equalities $\{ a^n b^n a^m b^m a^k \mid k,m,n\ge 1\}$. Etcetera. Note that we can get really fun things: For $ L ...
Hendrik Jan's user avatar
  • 30.6k
5 votes
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$...
Ziad Ismaili Alaoui's user avatar
4 votes
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 "...
Pseudonym's user avatar
  • 22.1k
4 votes

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 ...
Mati's user avatar
  • 63
4 votes
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 \\ ...
Hendrik Jan's user avatar
  • 30.6k
3 votes

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 ...
Hendrik Jan's user avatar
  • 30.6k
3 votes
Accepted

CFG {$w\in ${a,b,c}$^* | $#$_a(w) + $#$_b(w) = $#$_c(w)$}

You are interested in the language $L = \{w\in \{a,b,c\}^∗\mid \#_a(w)+ \#_b(w)= \#_c(w) \}$ but question how to haave the symbols in arbitrary order. You have solved $\{w\in \{a,b\}^∗\mid \#_a(w)=...
Hendrik Jan's user avatar
  • 30.6k
3 votes
Accepted

The complement of a particular language

The complement of the language $L = \{a^nb^n : n \in \mathbb{N}\}$ should actually be linear, if I'm not mistaken. Take some string $x \notin L$ over the alphabet $\Sigma = \{a, b\}$, since $L \...
Knogger's user avatar
  • 1,032
3 votes
Accepted

Accept $L=\{ww^r:w\in\Sigma^*\}$ in less that $|w|$ storage

It is (obviously) possible if $|\Sigma| = 1$ or $C = 1$. It is also possible for $|\Sigma| > 1$ and $C>1$. The idea is that you can use a bigger stack alphabet to encode multiple letters at once....
Nathaniel's user avatar
  • 15.4k
3 votes
Accepted

Is there a linear language $L$ such that $\overline{L} \in \texttt{Type-2} \setminus \texttt{Lin}$?

It seems you almost solved the problem in your question statement. Note that the $n\neq m$ condition makes pumping hard: one needs a trick using factorials to succeed, see Prove if $L=\{0^m1^n∣m≠n\}$...
Hendrik Jan's user avatar
  • 30.6k
3 votes

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 ...
Hendrik Jan's user avatar
  • 30.6k
3 votes

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....
Hendrik Jan's user avatar
  • 30.6k
3 votes
Accepted

A context-sensite grammar for the language of sequences of two different types of parentheses with possible intersections?

Basically, the idea is that $($ and $)$ can commute with $[$ and $]$, but $($ cannot commute with $)$ – and same for $[$ and $]$. An essentially noncontracting grammar would be: $S \to \varepsilon \...
Nathaniel's user avatar
  • 15.4k
2 votes
Accepted

An elementary question about grammar

You are close, but not precise. Usually one distinguishes between the arrow notation for the rules $A \to aA$ and the notation for derivation in the grammar, that is the application of the rules in ...
Hendrik Jan's user avatar
  • 30.6k
2 votes
Accepted

Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s

Intuitively you cannot check palindromicity and (un)equality of numbers using a single pushdown, so also $P'$ must be non-context-free. Formally proving unequal-repeating-numbers to be non-context-...
Hendrik Jan's user avatar
  • 30.6k
2 votes
Accepted

Is L={0^n 1^n ∣n≥0} context free language?

You have just shown that the given language does not meet the condition of the pumping lemma for $n=5$ and one particular decomposition. To conclude that $L$ is not context free you need to show that ...
Steven's user avatar
  • 29.4k
2 votes

What's really meant by context-free in the term context-free grammar?

What's meant by "Context Free"? Ultimately that the applicability of a phrase structure rule, for a grammar, should be independent of the surrounding context, where it is applied. The fact ...
NinjaDarth's user avatar
2 votes

Are there context-free languages whose both intersection and complement of intersection are non-context-free?

We can build a specific example over the alphabet $\{a,b,c\}$ as follows. Let $L_1 = \{ a^k b^m c^j \mid j < m \lor k < m \}$ and $L_2 = \{ a^k b^m c^j \mid k < 2m \}$. Obviously, $L_1 \cap ...
Mati's user avatar
  • 63
2 votes

Are there context-free languages whose both intersection and complement of intersection are non-context-free?

Here is a recipe to construct such a language, using examples we know. Start with a context-free language $K_0$ such that its complement $K_0^C$ is not context free. Also consider two context-free ...
Hendrik Jan's user avatar
  • 30.6k
2 votes

How to prove that $L = \{{a^{n} b^{n} c^{j} | n,j \geq 0}\}$ is a CFL?

Proving that the pumping lemma (for context free languages) holds for some language $L$ provides no information on whether $L$ is context-free (since the pumping lemma is just a necessary condition). ...
Steven's user avatar
  • 29.4k
2 votes
Accepted

Is the language accepted by a DFA with a fixed word on the stack after consuming it a deterministic context free language?

Yes, $L$ is a deterministic context-free language. I will describe how to build a deterministic pushdown automaton $\mathcal{M}'$ to recognize $L$. The stack alphabet of $\mathcal{M}'$ is $\Gamma' = \...
D.W.'s user avatar
  • 159k
2 votes
Accepted

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

While the answer by Hendrik Jan is correct. Here is a concrete example. Consider a CFG $G$ with the following rules $S \to aSb|\epsilon$. It is not hard to see that $L(G) = \{a^n b^n: n\geq 0\}$, and ...
Bader Abu Radi's user avatar
2 votes
Accepted

How to construct context-free language $L$ to prove $L′=\{x|xx∈L\}$ is not context-free?

Take a look at $$L = \{a^nb^nc^ma^mb^kc^l : n, m, k, l \geq 0\}.$$ Now take some $x \in L$ with $x = ww$, then $x = a^nb^nc^ma^mb^kc^l$ for some $n, m, k, l \geq 0$. There's only one possible way to ...
Knogger's user avatar
  • 1,032
2 votes

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

Suppose that instead of a stack, you had a single counter, $x$, that you could either increment or decrement, under the control of a non-deterministic finite-state machine. (Each transition of the ...
D.W.'s user avatar
  • 159k
2 votes

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 ...
ruakh's user avatar
  • 633
2 votes
Accepted

Context free grammar for $L=\{a^nb^m : 2m<n<4m\}$

The problem with your (new) solution is that you force $n$ to be equal to $3m$. That means that your grammar generates words that are in $L = \{a^nb^m\mid 2m < n < 4m\}$, but words in $L$ like $...
Nathaniel's user avatar
  • 15.4k

Only top scored, non community-wiki answers of a minimum length are eligible