Say I have a grammar e.g,

$$\begin{align}S&\to AB\mid abc\\ A&\to aAb \mid \lambda\\ B&\to bBa \mid ba \end{align}$$

Now it is obvious the notation for this would be something like, $$L(G) = \{a^{i}b^{i}b^{k}a^{k} | i \ge 0, k > 0\}$$

My question is how do I account for the starting state going to abc. How can I represent this in set notation? My only thought would be to append $(abc)^{m}$ to the statement and then say something like if i,k == 0 then m = 1. Though I'm not sure if that is allowed?

  • 2
    $\begingroup$ Why not just use set union? $\endgroup$ – rici Mar 25 at 20:02
  • 1
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Mar 25 at 21:41

In contrast to popular thought, the description of a language doesn't have to be of the exact form $$ L = \{a^i b^j c^k \mid \text{conditions on $i,j,k$}\}. $$ A language is a set, and you can describe it in exactly the same variety of ways as you describe sets. For example, we can write $$ L = \{a,b\}^* \setminus \{a^nb^n \mid n \geq 0\}. $$ In your case, as rici mentions in the comments, you might as well just take a union with $\{abc\}$ to account for the additional case.

| cite | improve this answer | |

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.