The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

0

A handle is a production whose right-hand side can be reduced at a specific moment during a parse. (Or, as it is usually presented, it is the production which has been expanded at a specific point in a derivation for a sentence.) Although a handle is almost always defined as a production, it's common to talk about them as though they were just the right-hand ...

0

The square language $L^2$ is defined as follows: $$L^2 = LL = \{ xy : x,y \in L \}.$$ There is no requirement that $x = y$. Indeed, in your case $L^2 \supsetneq \{ w^2 : w \in L \}$.

2

Your approach won't work. Whenever you try to match the length of two non-terminals, that should be a big red flag your approach won't work. Here's a hint: expand from the middle out, after starting with $S = a \mid b \mid aAa \mid bBb$. Can you take it from here?

2

The idea is to start with a grammar for the related language $L'_2 = \{a^ib^j \mid 2j \leq i \leq 3j\}$: $$S \to a^2Sb \mid a^3Sb \mid \epsilon.$$ We want to force at least one production of the form $a^2Sb$ and at least one of the form $a^3Sb$. There are many ways of doing that. The simplest, probably, is to force one of these productions to be the first, ...

2

Equal numbers of a’s on either side, then the middle is replaced by a+b or by ba+.

0

Since this seems very much like homework, i will give you a little Hint, taking as example a sub-case of your language: The GFC for the string $a^3b^3$ is the following: $S ⇒ aSb$ $aSb ⇒ aaSbb$ $aaSbb ⇒ aaaSbbb$ $aaaSbbb ⇒ aaabbb$ You can take the above as a starting point from which to adapt the grammar to your case.

0

proving kleene closure of DCFL is not DCFL

2

Any regular language upholds the pumping lemma. Hence, if a language doesn't uphold the pumping lemma, it is not a regular language. This is in fact the standard way of proving a language is not regular. Let us choose $p$ to be the pumping length. Let's now take $0^n=1^n \oplus 1^n$, which is in $A$. This string can be decomposed into three concatenated ...

0

Above answers are excellently written. But one other approach would be helpful I think. We want to prove that if $L(A)$ is a $CFL$ and $L(B)$ is a regular then $L(A/B) = \{w\space|\space wx \in A,\space x\in B,\space w\in \Sigma^*\, ,\space x\in \Sigma^*\}$ is also a $CFL$. Let's use fact that set of regular languages and set of context free languages are ...

Top 50 recent answers are included