4
$\begingroup$

The question is to design a CFG for the language of words that have as many c's as the difference of numbers of a's and b's, that is

$\qquad\displaystyle L = \{(a^l)(b^m)(c^n) \mid l, m \in \mathbb{N}; n = |l-m|\}$.

I have so far go to create the cfg for $(a^l)(b^m)$ but don't know how to do the one for $(c^n)$. It looks complicated as to find the value of n, we need to take the abs value for the difference between l and m. Can someone help?

And, here is the cfg I got so far for $(a^l)(b^m)$.

$S \to aS \mid bT|\epsilon $

$T \to bT \mid \epsilon$

I hope this is correct.

$\endgroup$
  • $\begingroup$ There are many similar questions, see e.g. here. $\endgroup$ – Raphael Nov 2 '13 at 9:59
2
$\begingroup$

Yuval's answer is headed in the right direction: consider $L_1 = \{a^lb^mc^n \mid n = l - m\}$ and $L_2 = \{a^lb^mc^n \mid n = m - l\}$. Also, as he points out, it's helpful to think of these conditions as $l = n+m$ and $m = n + l$, respectively.

I propose the following grammar for $L_1$: $$S' \rightarrow aS'c \mid B' \mid \epsilon$$ $$B' \rightarrow aB'b \mid \epsilon$$

I propose the following grammar for $L_2$: $$S'' \rightarrow A''C''$$ $$A'' \rightarrow aA''b \mid \epsilon$$ $$C'' \rightarrow bC''c \mid \epsilon$$

Now, what remains is to show these grammars generate $L_1$ and $L_2$, after which you can give your answer as the following: $$S \rightarrow S' \mid S''$$

(You could even use just one symbol for $B'$/ $A''$, since they have the same rules.)

To show each of the proposed grammars works, you'll need to show two things: each proposed grammar generates only strings in the target language; each proposed grammar generates all the strings in the target language.

Arguing informally, we can say the proposed grammar for $L_1$ generates only strings in $L_1$ since whenever we add an $a$, we add either a single $b$ or a single $a$; furthermore, we have all $b$ coming after $a$, and all $c$ coming after $b$. To show that all the strings are generated, consider that applying the rule $S' \rightarrow aS'c$ a number of times equal to $\#_c(w)$, then the rule $S' \rightarrow B'$, then the rule $B' \rightarrow aB'b$ a number of times equal to $\#_b(w)$, then the rule $B' \rightarrow \epsilon$, yields the string $w = a^{\#_b(w)+\#_c(w)}b^{\#_b(w)}c^{\#_c(w)} \in L_1$ for any non-negative $\#_b(w), \#_c(w)$.

The arguments for the second proposed grammar are similar.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Patrick87, you understand you are solving the OP's homework assignment for them? Given the OP's work so far, it seems they'll have a hard time during the final exam, especially if they don't even solve their homework assignments on their own. $\endgroup$ – Yuval Filmus Nov 1 '13 at 17:29
  • $\begingroup$ @YuvalFilmus I understand that it's a very real possibility, yes. However, the rationale I've found myself employing in answering these questions is to try to make no assumptions whatsoever about the intentions or motivations of the people asking them - or, rather, to assume the very best intentions and motivations. In cases like this, the thought process is roughly as follows: maybe it's not homework; maybe it is homework, but it's not graded; maybe it's homework and is graded, but the asker has integrity; etc. Of course, even if the intentions are bad, the answer might help somebody else. $\endgroup$ – Patrick87 Nov 1 '13 at 18:08
  • $\begingroup$ See here for one way of proving rigorously that a grammar generates the wanted language. It applies readily here. $\endgroup$ – Raphael Nov 2 '13 at 10:05
1
$\begingroup$

Hint: Break $L$ into two languages, $L_1 = \{ a^l b^m c^n : n = l-m \}$ and $L_2 = \{ a^l b^m c^n : n = m-l \}$. The conditions are probably better written as $l = m+n$ and $m = l+n$, respectively.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How would I use conditions such as l = m+n or m = l+n in a cfg? $\endgroup$ – SSH Oct 31 '13 at 22:34
  • $\begingroup$ That's a question for you. I can't give away the answer. $\endgroup$ – Yuval Filmus Nov 1 '13 at 0:23
0
$\begingroup$

Note that you can as easily construct a pushdown-automaton and use the standard translation. That's not very insightful in terms of learning how to build grammars, but it works.

In this case, note that $c^+$ is the last block, so all an automaton has to do is to have $|l-m|$ symbols on the stack upon reaching the first $c$.

| cite | improve this answer | |
$\endgroup$

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.