The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote
Can someone give the intuition behind this ? Moreover an example will also be helpful ..
asked in Theory of Computation by Loyal (7.4k points) | 1.5k views

1 Answer

+3 votes
Best answer

Let $x_1, x_2, x_3, \ldots$ be the sequence $0, 1, 4, 6, 8, 9, \ldots$ of non-prime, non-negative integers.

Let $a^{x_i}$ be a string of $x_i$ number of $a$’s (that is, $a^{x_3} = a^4 = aaaa$)

Let the language $L_i = a^* - \left \{a^{x_i} \right \}$.

Now consider $L =$ The infinite intersection of the sequence of languages $L_1, L_2, \ldots$. That is, $$L = \bigcap_{i=1}^{\infty}L_i = L_1 \cap L_2 \cap L_3 \cap \ldots$$

Note that $L = \left \{a^p \mid p \text{ is prime}\right \}$.

Hence L is not regular.

Another easy example would be (this one with unions as opposed to intersections):

Let $L_i = \left \{a^i b^i \right \}$ for some given value $i$.

Then, $L_1 = \{ab\}, L_2 = \{aabb\}, L_3 = \{aaabbb\}$ and so on.

Now consider $L =$ The infinite union of the sequence of languages $L_1, L_2, \ldots$ That is, $$L = \bigcup_{i=1}^{\infty}L_i = L_1 \cup L_2 \cup L_3 \cup \ldots$$

Thus, $L = \left \{ a^i b^i \mid \forall i > 0 \right \}$ which is CFL but not Regular.

answered by Boss (40.8k points)
Are you sure that a^(xi ) where xi is not prime is a regular language ?
@Aryana: No, $\left \{a^{x_i} \mid x_i \text{ is not prime} \right \}$ is not regular. However, Leen never claimed that it was.

When Leen said $L_i = a^* - \{a^{x_i}\}$, that $i$ is just one index. So $L_i$ is regular.

Then the infinite intersection $L = \bigcap_{i=1}^{\infty} L_i$ is not regular.
how is Li regular?

Li is a regular language on 'a' which contains length of all strings except axi where xi is a non prime no.

How do we draw a DFA for it? If we were asked to make a DFA accepting strings of length not equal to 'n' where n is non prime no., then we would make a DFA having (n+2) states where the (n+1)th state would be the only non-final one.

But here there is no upper bound on the non-prime no.,xi. It can go upto infinity. How can i make a finite automata?

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
49,532 questions
54,123 answers
71,044 users