# Tag Info

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 ...
• 456
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 ...
• 507

• 39k

### 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 ...
• 72.4k

### 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}$, ...
• 72.4k
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$ ...
• 7,455
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\}$. ...
• 39k
Accepted

• 277k

### 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 ...
• 277k

### 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 "...
• 14k
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 ...
• 277k

### 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 ...
• 463
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 ...
• 12k
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*} &...
• 72.4k