I have a language like this and will need to write the Context-free grammar for it.
$$\{a^n b^m c^k\; : \;k = |n-m|,\; m, n, k \geq 0\}$$
What I am confused is do I need to simplify the condition of k = |n-m| to solve or it just means the length
Asked
Active
Viewed 1.4k times
2
-
$c^{n} \over c^{m}$, eliminating k the parameter? – Don Larynx Aug 25 '13 at 00:47
-
@Jossie, huh? You cannot divide here... – Mariano Suárez-Álvarez Aug 25 '13 at 00:55
-
@MarianoSuárez-Alvarez k = m - n. – Don Larynx Aug 25 '13 at 01:02
-
@Jossie Perhaps you don't understand the expression - $a$, $b$ and $c$ are symbols, not numbers. You cannot 'divide by' powers of $c$. – Steven Stadnicki Aug 25 '13 at 01:03
-
Sorry. Please excuse my comments – Don Larynx Aug 25 '13 at 01:06
2 Answers
2
You can do one thing, $k=n-m$ is the required condition, so we can show that $n=m+k$, i.e for every $b$ there must be an $a$ and for every $c$ there must be an $a$. So the language can be written as:
S -> aSc | aTb
T -> aTb | ab
-
Welcome to math.SX! In order to make your answer easier to read and understand, please format your post. – Mårten W Sep 28 '16 at 14:34
2
Consider breaking it into the two cases $n\geq m$, $k=n-m$ and $m\gt n$, $k=m-n$; if you can find grammars for these two cases then you can just union them together to get your final CFG. As a further hint, note that in each case you can eliminate the larger of $m$ and $n$ in favor of $k$ and the smaller one; for instance, in the case $n\geq m$ then $n=m+k$ and so that 'half' of the grammar can be written as $a^{m+k}b^mc^k$ - or, more suggestively, $a^ka^mb^mc^k$. Can you see where to go from here?
Steven Stadnicki
- 51,746
-
Thanks, I came up with this: S -> X; X -> aXc|aUb|epsilon; U -> aUb|epsilon – Herious Aug 25 '13 at 01:04
-
@Herious That should work, although you probably want just 'U' rather than 'aUb' in the first expression; remember that you might have $m=0$. You should be able to handle the other case ($m\geq n$) in much the same way; can you see how? – Steven Stadnicki Aug 25 '13 at 01:11
-
-
Yep - and that should be an easy CFG to write (it starts, for instance, 'Y->VW' where V handles the $a^nb^n$ portion and W handles the $b^kc^k$ portion). Well-done! – Steven Stadnicki Aug 25 '13 at 01:15
-
yeah thanks a lot, I got this: Y -> VZ|epsilon ; V -> aVb|epsilon ; Z -> bZc|epsilon – Herious Aug 25 '13 at 01:21
-
yeah and I think from the beginning, the absolute value would be divided into 2 cases with OR connection, so I would write S -> X|Y|epsilon , is that correct? – Herious Aug 25 '13 at 01:22
-
@Herious Exactly, although the 'epsilon' is actually redundant there (and in fact, it's redundant in Y's definition as well) since both productions for S (and both parts of Y) can produce empty strings themselves. – Steven Stadnicki Aug 25 '13 at 01:24