The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

check whether given language is regular or not


1)   (ann where n ≥1

2)   ( an where n ≥ 1

3)  w= { (( a n) *  (( a)2 )*  } where n ≥ 1

asked in Theory of Computation by (383 points) | 103 views
I think L1 is not regular

L2 is regular

L3 is regular
2 and 3 regular ...1st one is not regular..

Language i.e accepted by first is

{a,a^4,a^9,.......} ,as its not in AP so you cant make any FA..

second accept language as. if i consider m>=1


third accept language as

{€,a^2,a^4,a^6.......} for this you can make FA..

can you please explain L3 briefly...

how {€,a^2,a^4,a^6.......} this series came from  { (( a n) *  (( a)2 )*  } 

@rahul rathod

when n=1 what will be the strings generated by the language


same way if you put n=2 you will get

{€,a^4,a^8, ... }.{€,a^4,a^8...}={€,a^4,a^8...}

so further all languages generated will be a subset of language generated by n=1, so languages generated is

Let p1=$((a^{2})^{n})^{*}$

P2=$((a^{n})^{2})^{*}$ both p1 and p2 is regular so there concatenation is regular

In case someone is finding L3 hard to understand:

P2, i.e. $((a^n)^2)$* is actually p1 only. See carefully. Both are (a2n)*. So now you can see why L3 is regular.

1 Answer

+1 vote

L1 is not regular we will not have the string in A.P only a,a^4,a^9,......

L2 is regular i.e if m=2 a^2,a^4,a^8,.....

L3 is also regular only i.e p1= (( a n) * is regular 

p2=(( a)2 )*  is also regular only

concatenation of two regular is regular only.

answered by (477 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,516 questions
48,528 answers
63,374 users