5
$\begingroup$

I have to generate a grammar for the language $L = \{ w \in \{ a, b\}^* \mid |w| \in 2\mathbb{N}, w \neq w^R\}$ and give the type of the language.

I've generated the grammar

$\qquad \begin{align} S &\to aSa \mid bSb \mid aAb \mid bAa \\ A &\to abA \mid baA \mid aaA \mid bbA \mid \varepsilon \end{align}$

This grammar is a context free grammar. I now can say that $L$ is a context free language. But how can I say for sure that this language isn't regular ?

Improve this question
$\endgroup$
1
  • $\begingroup$ First, you need to prove that your grammar really generates $L$, otherwise you know nothing. Second, see here for multiple techniques for showing that some language is not regular. $\endgroup$
    – Raphael ♦
    Feb 2, 2013 at 14:18

3 Answers 3

Reset to default
4
$\begingroup$

Regular languages are closed under complement and intersection. The complement of $L$, intersected with the regular $\{w : |w| \equiv 0 \pmod{2}\}$ is the language of even palindromes. If you must, you can easily show that it is not regular using pumping lemma.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Could you please tell me how could i use the pumping lemma. I know that it's used to show that a language it's not regular.I use the negated form of the pumping lemma.In order to do so i usually have a language that has a form like a^k b^ k(or something close to that).After this I choose an i so such that xy^iz does not belong to the L.I don't know from where to start with the pumping lemma in this example $\endgroup$
    – user1934980
    Feb 2, 2013 at 12:56
  • $\begingroup$ i've managed to demonstrate that palindromes are not regular.Thanks for the tip :) $\endgroup$
    – user1934980
    Feb 2, 2013 at 13:29
  • 1
    $\begingroup$ @user1934980, it would be hard to apply pumping lemma to $L$ directly, because so few words (of even length) don't belong to it. That is why I suggested to assume it is regular, transform it and then show a contradiction. $\endgroup$
    – Karolis Juodelė
    Feb 2, 2013 at 13:31
1
$\begingroup$

Your grammar is almost correct except for the fact that you cannot derive any word. Thus, it produces the empty language. However, as I said, the idea to produce a "difference" and then switch to another nonterminal is correct.

To prove that a language (no matter which one) is not regular, you can use the pumping lemma or, if you need it a little simpler, a proof by contradiction using a pumping argument.

Note, however, that the pumping lemma cannot be used to prove the converse.

Improve this answer
$\endgroup$
-2
$\begingroup$

Language categories are sets, and the context-free language set contains the regular language set. In other words, every regular language is context-free. It's useful to know that context-free contains LR, which contains LL, which contains regular.

Your language is regular because its definition conforms to the regular definition (strings that can be formed over an alphabet by applying the operations of concatenation, union, and closure).

There's an algorithm for converting a regular definition into a grammar. I believe that the algorithm would produce the following grammar for your language:

S -> aS
S -> bS
S -> ε

I'm not quite sure that the grammar you posted corresponds to the regular language definition. It's better to stick to proven stuff.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ No, this grammar would produce all words over a,b. $\endgroup$
    – Dan
    Feb 2, 2013 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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