I am having trouble understanding if my production rules are context-free grammar or not

230 Views Asked by At

From my understanding, a context-free grammar (CFG) is any set of production rules that does not contain any $\lambda$-productions and moreover non-terminal symbols cannot reproduce themselves. The formal definitons states that CFGs are simply a set of production rules that are one-to-one, one-to-many, or one-to-none which sounds a little ambiguous. All the examples of simple CFGs give the same rules which are pretty much: $$ \begin{align*} S &\rightarrow AA \\ A &\rightarrow \alpha\ |\ \beta \end{align*} $$ and that makes sense, but my problem is that from these kinds of simple examples I cannot tell if I am actually producing a CFG.

One of the questions for my homework asks:

Find a CFG for the language: $L = \{a^n b^n :$ n is a multiple of 3$\}$

My answer: $$ G = (\{S,A,B\},\{a,b\},S,P)\\ \begin{align*} S &\rightarrow A \\ A &\rightarrow aaabbb \\ A &\rightarrow B \\ B &\rightarrow aaaAbbb\\ \end{align*} $$

But I feel like I am missing something because I cannot tell if this is correct.

1

There are 1 best solutions below

0
On BEST ANSWER

So, taking into account the comments, the following CFG will do the job: $$ \begin{align*} S &\to \lambda\\ S &\to aaaSbbb \end{align*} $$