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

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 (381 points) | 92 views
0
I think L1 is not regular

L2 is regular

L3 is regular
+1
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

{a,aa,aaa,aaaa....}=a*

third accept language as

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

can you please explain L3 briefly...

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

0
@rahul rathod

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

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

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

{€,a^2,a^4,a^6,a^8....}
+1
Let p1=$((a^{2})^{n})^{*}$

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

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 (459 points)


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

39,657 questions
46,732 answers
140,421 comments
58,140 users