-1
$\begingroup$

Can someone please give a couple of examples of the language and construct a grammar for the language (given below), or at least show me how I can go about it?

I am looking for a context-free grammar generating the language

$$ L = \{ a^n b^m \mid n,m \geq 0 \text{ and } n \neq 2m \}. $$

I asked a similar question on stackoverflow, where it was closed.

After seeing that question one thing is very clear to me:

  1. Take care of the case when $n<2m$ (as in the stackoverflow question).
  2. Take care of the case when $n>2m$ (not sure how to do that).
$\endgroup$
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael May 22 '17 at 10:14
  • $\begingroup$ I am gaining understanding as this wasn't any homework...I was trying to solve the questions in the book Formal Automata by Peter Linz.. $\endgroup$ – Aditya May 22 '17 at 10:52
  • 1
    $\begingroup$ Moreover not everyone has excess to elite class professors who help there students...atleast in my case it isn't $\endgroup$ – Aditya May 22 '17 at 11:08
1
$\begingroup$

Let $G = (\{S\}, \{A, B\}, P, S)$ the formal grammar which production rules $P$ are:
$S \to aaSb \mid A \mid B \mid aB$
$A \to aA \mid a$
$B \to Bb \mid b$

We have $L(G) = L$.

Explanation:

  • $n < m$ : The $a$'s are generated in $S$. Whenever the count is right, the remaining $b$ are generated in $B$. If $n$ is odd, the production rule $S \to aB$ is used.
  • $m < n < 2m$ : Same as above.
  • $n = 2m$ : The only way to generate such a word is in $S$; if you branched to either $A$ or $B$, the hypothesis wouldn't hold anymore as you would prepend (resp. append) at least one $a$ (resp. $b$). As this symbol is nonterminal, this class of words isn't accepted.
  • $n > 2m$ : The $b$'s are generated in $S$, and the remaining $a$'s are generated in $A$.
$\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.