5
$\begingroup$

I have the following context-free language:

S -> ASa | b
A -> aA | a

I don't understand why this is not regular. I first said that it's generated by the regular expression a+ba+. The following is regular however

S -> ASa | b
A -> aA | e

e stands for the empty string. I don't understand their differences.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

The subtlety is that in the first case, the number of $a$'s before the unique $b$ must be at least the number of $a$ after, i.e. your language is $\{a^nba^m|n\geq m\}$, so it is not regular. This is because each $A$ produces at least one $a$.

In the second case however, this constraint disappears, and your language becomes indeed $b+a^*ba^+$ which is regular.

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

See, in the CFG grammar you need to store the value of n and m in order to compare the condition i.e. n>= m.So memory is required,preferably a stack.Whereas, in the regular grammar its either b or any string ending with ba. You don't need anything to remember to satisfy the grammar,as there is no such condition where you need to store the value.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I am not the original down-voter but your answer is very vague and, in parts, incorrect. What does it mean to say "in the CFG Grammar, you need to store the value of $n$ and $m$"? $n$ and $m$ are not mentioned anywhere in the question. And a grammar is just a set of rules for producing strings: you don't need to store any integers to do that. Why is a stack the preferred way to remember integers? The regular grammar does not generate $b$ or any string ending $ba$: for example, it includes $abaa$ but not $bba$. $\endgroup$
    – David Richerby
    Feb 14, 2014 at 12:49

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.