Consider the following two languages : L1 = {0i1j| gcd (i, j) = 1} L2 is any subset of 0*. Which of the following is correct ?
L1 is not regular and L2* is regular
Two separate facts are needed: whether a language that compares the counts of 0s and 1s is regular, and whether the Kleene star of a one-letter (unary) language is regular.
Step 1 — L1: suppose it is regular with pumping length p. Take a prime \(m \gt p\) and \(w = 0^{m}1^{m + p!}\); since \(\gcd(m, m + p!) = \gcd(m, p!) = 1\), w is in L1. The pumped part lies in the first p symbols, so it is \(0^{k}\) with \(1 \le k \le p\), and k divides p!. Pumping \(1 + p!/k\) times gives \(0^{m + p!}1^{m + p!}\), whose gcd is \(m + p! \gt 1\). This string is not in L1, a contradiction, so L1 is not regular.
Step 2 — L2*: if L2 is empty or {λ}, the star is {λ}, which is regular. Otherwise let g be the gcd of the lengths of the strings in L2. Sums of these lengths produce every multiple of g beyond some bound N (a Frobenius/Schur argument), so \(L_2^*\) is a finite set of strings shorter than N plus all strings \(0^{gk}\) with \(gk \ge N\). That set is regular, for every subset L2 of 0*.
So L1 is not regular while L2* always is; the choices that call L1 regular or L2* non-regular are wrong.
L1 is not regular and L2* is regular option is correct.
Similar Questions
Regular expression for the complement of language \(L = \{a^n b^m \mid n \ge 4,\ m \le 3\}\) is
Given two languages :
\(L_1 = \{(ab)^n a^k \mid n \gt k,\ k \ge 0\}\)
\(L_2 = \{a^n b^m \mid n \ne m\}\)
Using pumping lemma for regular language, it can be shown that
Which of the following statements is false ?
The regular expression corresponding to the language L where
\(L = \{ x \in \{0, 1\}^{*} \mid x\) ends with 1 and does not contain substring 00 \(\}\) is :
Let L be any language. Define even (W) as the strings obtained by extracting from W the letters in the even-numbered positions and even(L) = {even (W) | W ∈ L}. We define another language Chop (L) by removing the two leftmost symbols of every string in L given by \(\text{Chop}(L) = \{W \mid \nu W \in L, \text{ with } |\nu| = 2\}\).
If L is regular language then
For the above specified passage, which of the following represents the regular expression?
Which of the following properties correctly describe a Regular Grammar ?
(A) All production rules are of the form A→xB or A→x, where A and B are non terminal symbols and x is a terminal symbol.
(B) Regular grammars are more powerful than context-free grammars and can express any type of language.
(C) There is a direct correspondence between regular grammar and finite automata.
(D) Regular grammars can generate languages that are not recognised by any type of automata.
Choose the correct answer from the options given below :
The precedence of regular expression operators from lowest to highest precedence is:
Which of the following is TRUE about the Pumping Lemma for regular language?
The regular expression for the complement of the language L = {anbm|n ≥ 4, m ≤ 3} is :
Important Questions from Regular Languages
Which of the following are correct on regular expressions?
A. φ + L = L + φ = L
B. εL = Lε = L
C. φL = Lφ = φ
D. φL = Lφ = L
Choose the correct answer from the options given below:
- Let $L_1$ and $L_2$ be two languages over a finite alphabet, such that $L_1 \cap L_2$ and $L_2$ are regular languages.
Which of the following statements is/are always true? Regular expression for the complement of language \(L = \{a^n b^m \mid n \ge 4,\ m \le 3\}\) is
Given two languages :
\(L_1 = \{(ab)^n a^k \mid n \gt k,\ k \ge 0\}\)
\(L_2 = \{a^n b^m \mid n \ne m\}\)
Using pumping lemma for regular language, it can be shown that
- Let $\Sigma = \{a, b, c\}$. For $x \in \Sigma^*$, and $a \in \Sigma$, let $\#_a(x)$ denote the number of occurrences of $a$ in $x$.
Which one or more of the following option(s) define(s) regular language(s)?
