The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+1 vote

+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.

+3

@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.

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.

0

L_{i} is a regular language on 'a' which contains length of all strings except a^{xi} where x_{i} 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.,x_{i.} It can go upto **infinity**. How can i make a **finite** automata?

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,532 questions

54,123 answers

187,319 comments

71,044 users