7
$\begingroup$

Consider the language generated by the following context free grammar: $$ S \to SS \quad S \to () \quad S \to (S) \quad S \to [] \quad S \to [S] $$ There is a one-to-one correspondence between this language and rooted planar trees where each edge is either dashed or solid ([] corresponds to a dashed edge and () corresponds to a solid edge). Call a tree $T$ good if when you remove all the solid edges, the remaining dashed forest is a connected tree where all the vertices have valence $ \leq 2 $ (i.e a path). Let $L$ be the sublanguage consisting of all good trees.

Question: is $L$ context free?

It is easy to check that $L$ satisfies the pumping lemma for context free languages. My instincts tell me that it shouldn't be context free because you can only add square brackets (which correspond to dashed edges) in certain contexts, but I don't know if this intuition can be turned into a proof.

$\endgroup$

2 Answers 2

6
$\begingroup$

I think it's context-free and generated by roughly speaking the following 7 rules (but see Harry Altman's answer for more precision) $$S \rightarrow TUT,\quad U\rightarrow [TUT]$$ $$ U\rightarrow e,\quad T\rightarrow e$$ $$T\rightarrow (T)$$ $$T\rightarrow TT,\quad T\rightarrow ()$$ Here $S$ is the start symbol, $T$ represents an expression using (,) parentheses, $U$ builds up the [,] part, and $e$ is the empty string.

$\endgroup$
2
  • $\begingroup$ I think the first rule should be $S\to TUT$ instead. Also, this doesn't seem to allow the dashed path to begin below the root. $\endgroup$ Feb 4, 2015 at 1:26
  • $\begingroup$ Yes; ([]) should be allowed, but is not. $\endgroup$ Feb 4, 2015 at 1:47
4
$\begingroup$

As Bjørn says, it is context-free, but I don't think his solution is quite right. Here's a set of rules I think does work, where $S$ is start and $e$ is the empty word:

$S\to TST$

$T\to(T)$

$T\to TT$

$T\to e$

$S\to(S)$

$S\to U$

$U\to TUT$

$U\to [U]$

$U\to e$

Here, $S$ is the start, and represents any word in $L$. $T$ represents a tree with only solid lines. $U$ represents a tree in $L$ whose dashed path begins at the root (the dashed path may be empty).

The part with the $T$'s and the $U$'s is essentially identical to Bjørn's solution; the additional trickery with the $S$'s is to allow the dashed path to begin below the root.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.