2,374 views
1 votes
1 votes

Which of the following languages are regular and why

a) L= {a n!  :n>=1}

b)L= {an  :n is a perfect square}

c)L= {an  :n is not a perfect square}

d)L= {an  :n is not a prime number}

3 Answers

Best answer
2 votes
2 votes

a) L= {a n!  :n>=1}

L={a^1 ,a^2, a^6.........}

IF the string length is in arithmetic progression then we can iterate the common difference in DFA but in above language the string length of strings are not in arithmetic progression so it is not regular. same is applicable for the remaining languages

b)L= {a :n is a perfect square}

c)L= {a :n is not a perfect square}

d)L= {a :n is not a prime number}

suppose if L={a^n/ n is even}

L={a^0, a^2, a^4..............}

here the string lengths of language is 0,2,4,6,8 so, it is in A.P. difference is 2.                

                                        Hence language is  regular.

selected by

Related questions

1 votes
1 votes
1 answer
4