32 votes
Accepted

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

The context can be explained with regards to the production rules allowed for different grammars in Chomsky hierarchy. If you consider context-free grammars, their production rules have the following ...
PieCot's user avatar
  • 456
24 votes
Accepted

Can there be 'dead states' in a context-free grammar?

Context-free grammars are allowed to contain unproductive rules. This is accepted, because every CFG generates the same language as some proper CFG which contains no unproductive rules, no empty ...
ilke444's user avatar
  • 507
24 votes

Why are CFLs not closed under intersection?

Let us assume $2$ CFLs $L_1$ and $L_2$ and their corresponding grammars be $S_1$ and $S_2$ respectively. It is very straightforward to see that the union of the two, represented by the new grammar as $...
Akash Mahapatra's user avatar
19 votes
Accepted

Is Python a context-free language?

Context-free grammars cannot express the rules of INDENT/DEDENT and so Python (which we use today in practice with INDENTs/DEDENTs)is not pure CF. Parsers (or lexical analyzers or lexers) for these ...
fade2black's user avatar
  • 9,837
18 votes
Accepted

Is it decidable whether a given context free grammar generates an infinite number of strings?

Let $G$ be a context free grammar, and let us assume that it is in Chomsky normal form. If it's not, we'll convert it first. An important property of this normal form is that the only way to derive ...
Shaull's user avatar
  • 17.2k
18 votes

Different between left-most and right-most derivation

Given a derivation tree for a word, you can "implement" it as a sequence of productions in many different ways. The leftmost derivation is the one in which you always expand the leftmost non-terminal. ...
Yuval Filmus's user avatar
18 votes
Accepted

Can a language be context free and not have a BNF grammar?

No. If a language is context-free, it has a BNF grammar, by definition. A context-free language is a language with a context-free grammar, and a context-free grammar is a grammar written in BNF with ...
rici's user avatar
  • 12k
17 votes

Context-free Languages closed under Reversal

There is another way to look at this problem. Consider that the Language $L$ is a CFL. This means that there is a grammar $G=\{N,\sum,P,S\}$ that satisfies the CFL. We can assume that this is in ...
Ameet Deshpande's user avatar
17 votes

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

"Context" is surrounding text. Context-free grammars are context-free in the sense that the rules look like $A\to\text{things}$, rather than $\text{stuff}\,A\,\text{more-stuff}\to\text{things}$. The ...
David Richerby's user avatar
17 votes

Are all finite languages context-free?

The language consisting of the words $w_1,w_2,\ldots,w_n$ is generated by the context-free grammar $$ S \to w_1 \mid w_2 \mid \cdots \mid w_n. $$
Yuval Filmus's user avatar
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
15 votes
Accepted

Complement of CFL is Recursive

You can think of it as " every CFL is Recursive". And Recursive languages are closed under complementation. Therefore, if a language $L$ is CFL then it is also recursive and hence, $L^C$ is also ...
Akash Mahapatra's user avatar
15 votes
Accepted

What would you get if you add parameters to context free grammars?

Affix grammars (parameterised context-free grammars) were studied extensively by the eminent Dutch computer scientist Cornelis HA Koster, starting with his 1962 paper "Basic English, a generative ...
rici's user avatar
  • 12k
15 votes
Accepted

Prove or Disprove: an infinite intersection of regular languages is a context-free language

"I know that this statement is false, but couldn't find an example to disprove it." It might come as a surprise to you that, in fact, every non-context-free language can be a counterexample. ...
John L.'s user avatar
  • 39k
14 votes

Does a context-free grammar with multiple variables have a "starting" point?

What you have shown is technically not a grammar, only part of it. A grammar is formally defined as the tuple $(N, \Sigma, P, S)$, where: $N$ is a set of non-terminal symbols $\Sigma$ is a set of ...
svick's user avatar
  • 1,866
12 votes
Accepted

Is language equality for linear context-free grammars decidable?

Quoting from Amiram Yehudai, The Decidability of Equivalence for a Family of Linear Grammars, Information and Control 47, 122-136 (1980), page 1: The equivalence problem for various families of ...
reinierpost's user avatar
  • 5,519
12 votes

Conjecture: a half of a pairing context-free language must be a regular language

No, this conjecture is not true. Consider $A=\{0^n1^n \mid n\geqslant0 \}$ and $B=\{1^{2n}\mid n\geqslant0\}$. We have $\{|a| : a\in A\}=\{|b| : b\in B\}=\{2n\mid n\geqslant0\}$ and $A\bowtie B = \{ 0^...
John L.'s user avatar
  • 39k
11 votes

Is it decidable whether a given context free grammar generates an infinite number of strings?

Without loss of generality¹, assume that the input grammar $G$ does not have $\varepsilon$-rules² and is in reduced form. That is, every non-terminal appears in at least one derivation (starting ...
Raphael's user avatar
  • 72.4k
11 votes

How can the intersection of CFLs and REGs be CFL if REG is a proper subset of CFL?

You are confusing two different statements. $\mathrm{CFL} \cap \mathrm{REG} = \mathrm{REG}$ or, equivalently, for all $L_1 \in \mathrm{REG}$ : $L_1 \in \mathrm{CFL}$. For all $L_1 \in \mathrm{REG}$, ...
Raphael's user avatar
  • 72.4k
11 votes
Accepted

Is {a^n (a+b)^n | n>0} a Deterministic CFL?

You needn't determine the end of "first part". Note $L$ is exactly the set of strings satisfying the following three constraints: Its length is even. It only contains $a$ and $b$. The first $b$ ...
xskxzr's user avatar
  • 7,455
11 votes
Accepted

Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?

$\newcommand{\m}{\operatorname{\%}}$ Let $d(w)=(|w|-\#_a(w))\m3$, where $n\m 3$ is the remainder of dividing $n$ by $3$ as defined in almost every programming language. Note $L=\{ w\mid d(w)=0\}$. ...
John L.'s user avatar
  • 39k
10 votes
Accepted

Is intersection of regular language and context free language is "always" context free language

The claim is that the intersection of a regular language and a context-free language is context-free. You've intersected a regular language ($\{ab\}$) and a context-free language ($\{a^nb^n\mid n\geq ...
David Richerby's user avatar
10 votes

Does there exist context-free grammar with words of length n^2 or n^3?

For a language $L$, let $N(L) = \{|w| : w \in L\}$, and let $U(L) = \{1^n : n \in N(L)\}$. Parikh's theorem shows that if $L$ is context-free then $U(L)$ is regular. In particular, since $\{1^{n^2} : ...
Yuval Filmus's user avatar
10 votes

Does transforming a CFG to Chomsky normal form make it unambiguous?

There are inherently ambiguous context-free languages, and like all context-free languages they have grammars in Chomsky normal form, so transforming a CFG to Chomsky normal form doesn't necessarily ...
Yuval Filmus's user avatar
9 votes

In context-free grammar (CFG), what is the importance of doing both leftmost and rightmost derivations?

For one particular parse tree there are many possible derivations, depending on the order in which the expansions are done. In a sense, a parse tree represent all of the derivations you'd consider "...
vonbrand's user avatar
  • 14k
9 votes
Accepted

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

First, two remarks. When $L = (01)^*$, we have $\newcommand{\scramble}{\mathrm{SCRAMBLE}}\scramble(L) \cap 0^*1^* = \{ 0^n 1^n : n \geq 0 \}$, and this shows that we can't expect $\scramble(L)$ to be ...
Yuval Filmus's user avatar
9 votes

Can a queue automaton recognize palindromes?

The construction of a PDA except with a FIFO instead of a LIFO data structure attached can mimic any single tape TM as follows: it keeps the cell contents in the queue along with two special markers ...
MT_'s user avatar
  • 463
9 votes
Accepted

unambiguous grammar but it's not LR(1)

All $LR(1)$ grammars -- indeed, all $LR(k)$ grammars -- are unambiguous, by definition. But the converse is not true: the fact that a grammar is unambiguous does not say anything about whether it can ...
rici's user avatar
  • 12k
9 votes
Accepted

How can ws with |w| = |s| and w ≠ s be context-free while w#s is not?

Your proof is correct, and I was wrong. It took me a while to nail down where my confusion was, but with Yuval's help I think I got it. Let's consider the three languages $\qquad\begin{align*} &...
Raphael's user avatar
  • 72.4k
9 votes

Why are DCFL not closed under concatenation or Union whereas CFL is?

DCFL does inherit the closure property of its superset CFL: the union and concatenation of two DCFL languages are CFL. What doesn't hold is that the union and concatenation are necessarily ...
Yuval Filmus's user avatar

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