Show that language over unary alphabet is context free iff is regular.

[smith92]

Let L be language over unary alphabet {0}. Show that L is context free iff L is regular.
Could someone give me a hint how to solve this problem?

I solved similar problem: Show that L* is regular, but I still don't have idea how to solve previous.

Second problem could be solved in this way (e - empty word):

If L is empty or has only empty word, then L* has only empty word, so it is regular.
If L is not empty then exists smallest k that 0^k is in L.

We can define L = { w in L* | w mod k = i } and show that each L is regular language. L* is sum of L[0] ... L[k-1], so it is finite sum of regular language - it is regular language.

 

[vacuum]

For the first problem, we can use the fact that a language is context-free if and only if it can be generated by a context-free grammar. A context-free grammar is a set of production rules that can be applied to a starting symbol to generate strings in the language.

For a unary alphabet {0}, we can define a context-free grammar as follows:

S -> 0S | e

Where S is the starting symbol and e is the empty word. This grammar generates all strings in L by repeatedly adding a 0 to the beginning of the string or by generating the empty word.

Now, to show that L is regular if and only if it is context-free, we can use the fact that a language is regular if and only if it can be recognized by a finite automaton. A finite automaton is a machine with a finite number of states that reads input symbols and transitions between states based on those symbols.

For a unary alphabet {0}, we can define a finite automaton as follows:

Q = {q0, q1} - states
Σ = {0} - input alphabet
q0 - starting state
q1 - accepting state
δ(q0, 0) = q1 - transition from q0 to q1 on input 0
δ(q1, 0) = q1 - transition from q1 to q1 on input 0

This finite automaton recognizes all strings in L by starting in the state q0 and transitioning to q1 after reading a 0. The automaton stays in q1 for any additional 0s in the string, and accepts the string if it ends in q1.

Therefore, we have shown that L is context-free if and only if it is regular.