Register

GO Classes Test Series 2023 | Theory of Computation | Test 2 | Question: 3

• retagged by
332 views
3 votes
3 votes

Consider the following languages :

  1. $L_{1}=\left\{a^{k} b^{m} c^{n} \mid(k=m\right.$ or $m=n)$ and $\left.k+m+n \geq 2\right\}$
  2. $L_{2}=\left\{a^{k} b^{m} c^{n} \mid(k=m\right.$ or $m=n)$ and $\left.k+m+n \leq 2\right\}$
  3. $L_{3}=\left\{a^{k} b^{m} c^{n} \mid k+m+n \geq 2\right\}$

Which of the above languages are Regular?

  1. $\mathrm{L}_{2}$ Only
  2. $\mathrm{L}_{3}$ Only
  3. $L_{2}$ and $L_{3}$ only
  4. All
• retagged by
User Avatar

2 Answers

6 votes
6 votes

The point to be considered here is : 

if comparison → L is NON-REGULAR,

                         → Except L is finite

 

In L1: comparison & nonfinite → Non-regular

In L2 : comparison & finite → Regular

In L3: No comparison : >= k : regular

User Avatar
5 votes
5 votes
In $\mathrm{L}_{1}$, there is a matching between $\mathrm{k}, \mathrm{m}$ Or $\mathrm{m}, \mathrm{n}$; so, it is Non-regular but CFL. $\mathrm{L}_{2}$ is finite, so regular. $\mathrm{L}_{3}$ is regular because No matching required.
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

4 votes
4 votes
1 answer
1
GO Classes asked Jun 22, 2022
378 views
GO Classes Test Series 2023 | Theory of Computation | Test 2 | Question: 10
Let $\text{L}$ be a language over an alphabet $\Sigma$. The equivalence relation $\sim_{\text{L}}$ on the set $\Sigma^{\ast}$ of finite strings over $\Sigma$ ... $1$ Only $2$ Both None
Let $\text{L}$ be a language over an alphabet $\Sigma$. The equivalence relation $\sim_{\text{L}}$ on the set $\Sigma^{\ast}$ of finite strings over $\Sigma$ is defined b...
User Avatar
2 votes
2 votes
1 answer
4
GO Classes asked Jun 9, 2022
267 views
GO Classes Test Series 2023 | Theory of Computation | Test 1 | Question: 5
Consider the following statements : Any finite subset of $\{a, b\}^{\ast }$ is a regular language; For any regular expressions $\mathbf{r}$ and $\mathbf{s}$ ... $a$ Only $b$ Both None
Consider the following statements :Any finite subset of $\{a, b\}^{\ast }$ is a regular language;For any regular expressions $\mathbf{r}$ and $\mathbf{s}$, the regular ex...
User Avatar
Link Copied!