Complexity of CFG grammar for a regular language

Question

I know that each regular language can be generated by a CFG. This makes, in one sense at least: context-free languages more general than regular languages.

Are there known results about the 'complexity' of regular languages in the CFG context? For example, is it true that every regular language can be generated by an unambiguous LL(1) grammar? Or is something similar true?

The general question above comes from the attempts I made to build a 'simple' grammar generating $L=\{(ab)^i|(ba)^i : i\geq 0\}$. None of the grammars I could build were 'simple'.

Answer 1

A regular grammar is context-free. So regular languages are context-free.

Every regular language has a right regular grammar, which is simply derived from a finaite state automaton for that language.

Every regular language can be recognized by a deterministic finite state au tomaton. From that deterministic FSA you can construct a right regular grammar which is LL(1) since you can decide what to do for parsing by simply looking at the terminal on the rules applicable at any time. There always is only one such rule. Actually you do not even need the pushdown, and use the non-terminal for the states. (this is a bit informal, but it is so simple being formal seems silly).

The key part is producing the deterministic FSA.

So, yes, every regular language can be generated by a LL(1) grammar.

A LL(1) grammar is always unambiguous, as it allows constructing a deterministic push-down automaton. So it is unnecessary to specify that it is unambiguous.

As for your language, it seems strangely defined, and I wonder whether you copied that correctly. What is the "$+$" supposed to mean ?

Answer 2

Regular languages are described by regular grammars. These come in two varieties: left-regular and right-regular. Right-regular grammars encode the computation of an NFA: the non-terminals represent the states of the NFA, and the rules encode the transitions. Left-regular grammars do everything in reverse. This is the simple class of grammars you are looking for.

Answer 3

As beginner in CS, I also became interested in CFG descriptional complexity. First of all I considered its variables complexity and got the following results for the particular language $L = (ab)^* + (ba)^*$:

1. There exists CFG with two variables which generates $L$
2. There exist no CFG with one variable which generates $L$

For proving (1) we may just consider the following CFG $$ S \rightarrow bAa \mid A , \, A \rightarrow abA \mid \varepsilon$$ The second proposition is a bit more tricky. Suppose that there exists CFG $G = (\{S\}, \{a, b\}, P, S)$ such that $L = L(G)$. Every production is $S \rightarrow \alpha$ for some $\alpha \in \{a, b, S\}^*$. Say, $\alpha$ contains $k$ instances of $S$; for every $u_1, \ldots u_k$ define the $\widetilde{\alpha}(u_1, \ldots u_k) \in \{a, b\}^*$ to be the word obtained from $\alpha$ by substituting $u_1$ into the first instance of $S$, $u_2$ into the second and so on. Then $u_1, \ldots u_k \in L$ implies $\widetilde{\alpha}(u_1, \ldots u_k) \in L$: as $L$ is generated by $G$, one can derive $\widetilde{\alpha}(u_1, \ldots u_k) \in L$ by using $S \rightarrow \alpha$ and then deriving every $u_i$ from $S$'s. By using that we can prove that in right-hand side of every production $S$ can't be followed immediately by any symbol:

• if $S$ is followed by $a$, we have subword $Sa$ in $\alpha$, then we can derive $ba$ from $S$, thus we can derive the word which contains two $a$'s in the row, which obviously doesn't lie in $L$;
• if $S$ is followed by $b$, having subsword $Sb$ of $\alpha$ we can derive $ab$ from $S$ and thus obtain the word which contains two $b$'s in the row;
• if we have subword $SS$ of $\alpha$, we can derive $ab$ from the first $S$ and $ba$ from the second.

Also $S$ can't follow neither letter nor $S$ in right-hand side of every production. So $G$ can only have productions of sort $S \rightarrow S$ and $S \rightarrow w$ for $w \in L$. Thus $L(G)$ is finite, which is contradiction.

You can also look to the Grushka's paper: https://www.sciencedirect.com/science/article/pii/S0019995871905195