- #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 = { 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.
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: