636 views
1 votes
1 votes

 L = {an bam|n,m ≥ 0 and n = m mod 5} is regular

2 Answers

Best answer
3 votes
3 votes

Yes it is regular..Let us see how :

We know modulo will lead to finite number of remainders here ranging from 0 to 4..Hence we can decompose the given language as :

L = L1  U  L2........U  L5

where L1 =  bam  | m is a multiple of 5 say 5k and hence 5k mod 5 = 0 and hence n = 0

Similarly L2  =  abam |  m = 5k + 1 and n = 1

and so on till L5..

As these are clearly regular..

So their union will also be regular..

Hence the given language is a regular language..

selected by
0 votes
0 votes

Let us look at similar language for simplicity $a^{n} b a^{m}$ such that n = m mod 2.

We can draw FA for the language that consists of strings: {b,aba,baa,abaaa,...}

So this language is regular.

Similarly the above given langugage is regular.

edited by

Related questions

0 votes
0 votes
0 answers
1
2 votes
2 votes
1 answer
3
Anurag_s asked Aug 15, 2015
1,961 views
Answer True/False for the statements:S1: $L ≤_m \{0^n1^n \mid n ≥ 0\}$ then $L$ is decidable.S2: if $L$ is R.E. and $L’ ⊆ L$ then $L’$ is recursively enumerable...