333 views
2 votes
2 votes
Prove that the language {aN : N is a composite number} is not
regular.

2 Answers

1 votes
1 votes
- In order to prove that a number N is composite,  we need to prove that it has more than 2 factors i.e 1 and itself.

- This cannot be done with a fixed amount of memory as the number of cases to check increases as N increases

- As regular language has a finite amount of memory, proving that number N is composite is not regular

- The language can be recognised by a Turing machine.
1 votes
1 votes
  • With a choice of $m$, we pick w = $a^{n}$ : where n is composite and $n \geq m$
  • If $w = xyz$ , is the decomposition, then $y =a^k$ : where $0 \leq k \leq m$ because $|xy| \leq m$
  • Now, $w_i$ = $a^{n-k}.a^{ki}$
  • This $n+(i-1)k$ quantity is not always composite : for example $ n = 10 , i = 2 , k = 3 $ and we have $w_2$ is not in language.
  • Therefore, the language is not regular.

Related questions

0 votes
0 votes
1 answer
1
Aakanchha asked May 3, 2018
628 views
Let R(A, B, C) be a relation with primary key (A) and S(A, D, E) a relation with primary key (A, D). Each of the relations has n tuples. If the number of tuples in R natu...
0 votes
0 votes
1 answer
3
MiNiPanda asked May 9, 2018
565 views
Let R(A,B,C) be a relation with primary key (A) and S(A,D,E) a relation with primary key (A,D). Each of the relations has n tuples. If the number of tuples in R natural j...