- #1

smith92

- 2

- 0

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

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.*
Last edited: