0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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 ? $\endgroup$
    – J.-E. Pin
    Apr 23 '15 at 10:00
  • $\begingroup$ @J.-E.Pin The Pumping Lemma for Context-Free Languages. There are a lot of cases i think :( $\endgroup$
    – Zafer
    Apr 23 '15 at 10:18
  • $\begingroup$ But what do you want to prove? $\endgroup$
    – J.-E. Pin
    Apr 23 '15 at 11:21
  • $\begingroup$ It is not context free. I want to prove this. $\endgroup$
    – Zafer
    Apr 23 '15 at 11:38
1
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ 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 :) $\endgroup$
    – Zafer
    Apr 24 '15 at 21:08
  • $\begingroup$ @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. $\endgroup$ Apr 24 '15 at 21:15
0
$\begingroup$

The dollar symbol here acts as a delimiter symbol, it separates the three substrings of $a$s.

$\endgroup$
1
  • $\begingroup$ How can i use pumping lemma. $ is like comma? am i right? or not $\endgroup$
    – Zafer
    Apr 23 '15 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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