Question

Which of the following is a regular language?
(A) L1 = Set of balanced parenthesis where alphabet sigma={(,)}
(B) L2 = Set of all unary strings |sigma| = 1 of lengths equal to Fibonacci numbers
greater than 5 (i.e. 8, 13, 21, . . . .)
(C) L3 = Kleene closure of the language in option (B)
(D) None of these

Answer 1

Answer on Question #38962-Math-Math, Other

1) Let's prove that L1 is not regular. We can use pumping lemma. If L1 is regular, there exist such n that we can pump any balanced parenthesis longer than n. OK. Then we can do this n n

to this one: ( ) . Obviously, after pumping new parenthesis is unbalanced.

2) Let's prove that L2 is not regular. We can use pumping lemma again. There is no infinite sequence of Fibonacci numbers with constant difference between neighboring elements.

3) Let's prove that L3 is regular. Any Fibonacci number larger than 5 can be represented as $13x + 8y$. And any number from closure under addition of Fibonacci numbers larger than 5 can be too. Then we can use this prefix grammar:

$\Sigma$: {a}.

S: $\{\varepsilon\}$.

P:

$\varepsilon \rightarrow aaaaaaaa$;

$\varepsilon \rightarrow aaaaaaaaaaaa$.

Proved!

Answer: C.