# Dollar Sign in Context Free Language

I have a homework about find the pumping lemma in Context Free Language. The last one I couldn't solve:

$L = \{a^i \$ a^{3i} \$a^{5i} \mid i \in \mathbb{N} \}$

What does the dollar symbol mean in this language?

How can I use pumping lemma in this example?

Thank you in advance.

• The dollar symbol simply denotes a letter of the alphabet. You could use $b$ instead. But what do you want to prove by using the pumping lemma? And which pumping lemma do yo want to use ? Apr 23 '15 at 10:00
• @J.-E.Pin The Pumping Lemma for Context-Free Languages. There are a lot of cases i think :( Apr 23 '15 at 10:18
• But what do you want to prove? Apr 23 '15 at 11:21
• It is not context free. I want to prove this. Apr 23 '15 at 11:38

## 2 Answers

In theory there are several cases, but they all work exactly the same way and can be handled at once.

Start with the word $s=a^p\$a^{3p}\$a^{5p}$, where $p$ is the pumping length. The pumping lemma gives you a decomposition $s=uvwxy$ such that $|vwx|\le p$, $|vx|\ge 1$, and $uv^kwx^ky\in L$ for each $k\ge 0$. Because $|vwx|\le p$, the string $uvw$ can intersect at most two of the blocks of $a$s; use this fact to show easily that pumping $s$ takes you out of $L$.

• I take $like an letter from alphabet. And I've solved it already. But if it is delimiter, I don't know how to solve :) Apr 24 '15 at 21:08 • @Zafer: Yes, it’s a letter from the alphabet: the alphabet is$\{,\$\}$ (or some finite superset thereof). In terms of the language $L$, however, $\$$functions as a delimiter within words, separating the blocks of$a$s. Apr 24 '15 at 21:15 The dollar symbol here acts as a delimiter symbol, it separates the three substrings of$a$s. • How can i use pumping lemma.$ is like comma? am i right? or not Apr 23 '15 at 10:30