Defining a regular grammar but without $Q \rightarrow \varepsilon $

I defined a regular grammar (FSM), which starts with $ ab$ and ends with $ ba$ the following way:

  1. $ S \rightarrow aS$
  2. $ S \rightarrow bS$
  3. $ S \rightarrow aT$
  4. $ T \rightarrow bR$
  5. $ R \rightarrow aQ$
  6. $ Q \rightarrow aQ$
  7. $ Q \rightarrow bQ$
  8. $ Q \rightarrow \epsilon$

, where $ S$ is the starting element, $ \epsilon$ is the empty (null) element and the rest are just variables.

The rules 6, 7 and 8 are there, so we can end a word. However, I am trying to rewrite my grammer but without the $ Q \rightarrow \epsilon$ . I can’t use the empty element.

Can it be done? I’m not sure how.


Find equivalent LL(1) grammar

There is sample question to calculate equivalent LL(1) grammar for below grammar:

$ S \rightarrow S b$

$ S \rightarrow S d$

$ S \rightarrow c S$

$ S \rightarrow c c a$

At first step, it has left recursion so I remove it and convert it to bellow grammar:

$ S \rightarrow F M$

$ F \rightarrow c S$ (same as $ F \rightarrow c F M$ )

$ F \rightarrow c c a$

$ M \rightarrow \epsilon$

$ M \rightarrow b M$

$ M \rightarrow d M$

We can remove first collision of second and third part too:

$ S \rightarrow F M$

$ F \rightarrow c D$

$ D \rightarrow F M$ (same as $ D \rightarrow c D M$ )

$ D \rightarrow c a$

$ M \rightarrow \epsilon$

$ M \rightarrow b M$

$ M \rightarrow d M$

One more time remove first collision:

$ S \rightarrow F M$ (predict: c)

$ F \rightarrow c D$ (predict: c)

$ D \rightarrow c G$ (predict: c)

$ G \rightarrow D M$ (predict: c)

$ G \rightarrow a$ (predict: a)

$ M \rightarrow \epsilon$ (predict: b, d, $ )

$ M \rightarrow b M$ (predict: b)

$ M \rightarrow d M$ (predict: d)

Everything is solved except last part of grammar. I tried to solve it but I think there is no LL(1) grammar for this. Is it true? If not, Is it possible to help me? Thanks.

Is following grammar LR(0)?

I know how to verify whether grammar is LR(0) or not. But this particular case is little tricky and hence the question.


$ SL \rightarrow SL ; S \space | \space \epsilon$

$ S \rightarrow s$

(Note: $ SL$ is single non-terminal.)

Now, LR(0) automaton for this grammar is as follow:

enter image description here

Now my question is whether to consider entry $ start \rightarrow SL.$ in $ State_1$ as SR conflict.

Because I previously came to know that we don’t consider conflicts due to augmented production.


Developing a Context Free Grammar whilst knowing the number of terminals

I am trying to develop a CFG for the language $ L$ defined by:

$ L = \{a^{n+2}bba^{n-2} | n > 1\}$

The problem I am having is that I cannot develop the CFG for this language no matter what I try. The closest I can get is:

$ S \rightarrow aaaaXbbX$ (Production 1)

$ X \rightarrow aX | \Lambda $ (Production 2)

This would be right if we were somehow forced to substitute the same value of the non-terminal $ X$ in both its appearances in production 1. However, we can substitute $ X \rightarrow aX$ in its first apperance in production 1 and $ X \rightarrow \Lambda$ in its second appearance in production 1, thus throwing the balance of $ a’s$ off as defined in the language $ L$ .

The first question is, is there even a CFG for this?

Well, I would say according to theory, yes there is because:

  • I am asked to draw a Determinate Push Down Automata for this language; and
  • According to theory, every language accepted by a PDA is context-free

Am I correct that there is a CFG to this and what is it?