1
$\begingroup$

Given the alphabet $Λ = \{a, b, c\}$, i need to write a grammar for this language:

$$L=\{α \mid α∈Λ^+ ∧ aaa \notin α\}$$

I know that in my language the sequence of three consecutive $a$ cannot occur in any string, but how do I make a grammar of it? I'd need the thinking behind the construction of the grammar (like what's the first thing you should consider?), because so far I only manage to go by instinct and this doesn't always work.

$\endgroup$
  • $\begingroup$ This is a regular language, so you can construct an NFA and convert it into a grammar. $\endgroup$ – Yuval Filmus Jan 25 '17 at 11:56
  • $\begingroup$ From the NFA I constructed, that's the grammar that came out: $$ S → a | b | c | aA | bA | cA $$ $$ A →a | b | c | bA | cA | aB $$ $$ B → b | c | bA | cA $$ So i should always build the NFA before writing the grammar? With all kind of languages? $\endgroup$ – emaph Jan 25 '17 at 12:38
  • $\begingroup$ This is just one way to construct a CFG when the language happens to be regular. Of course, there are context-free languages which aren't regular, and this method wouldn't work for them. $\endgroup$ – Yuval Filmus Jan 25 '17 at 12:40
  • $\begingroup$ Indeed, for example with this non-regular language: $$ L= \{ aba^n b^m a^n |n,m>0 \} $$ what's the best way to start? Every string has to start with $ab$, then we have $aba$, and this part has to have the same number of $a$. $\endgroup$ – emaph Jan 25 '17 at 12:54
  • 1
    $\begingroup$ If you have a different question, ask it separately. $\endgroup$ – Yuval Filmus Jan 25 '17 at 13:02
0
$\begingroup$

Your language is regular, and so one way to construct a context-free grammar for it is to first consider a finite state automaton, and then convert it to a grammar. Of course, this methodology only works for regular languages, and is not necessarily the easiest way in every case.

$\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.