Regular Languages

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?

Consider the two lists List I and List II given below: List I (i) Context free languages (ii) Recursive languages (iii) Regular languages List II (a) Closed under union (b) Not clo...

Consider the following two languages over the alphabet {a, b}: L₁ = { αβα |α ∈ {a,b}+ AND β∈ {a,b}+ } L₂ = {αβα|α ∈ {a}+ AND β∈ {a,b}+ } Which ONE of the following statements is CO...

Let Σ = {a, b, c}. For x ∈ Σ*, and α ∈ Σ, let #α(x) denote the number of occurrences of α in x. Which one or more of the following option(s) define(s) regular language(s)?

Let Σ = {1,2,3,4}. For x ∈ Σ*, let prod(x) be the product of symbols in x modulo 7. We take prod(ε) = 1, where ε is the null string. For example, prod(124) = (1 × 2 × 4) mod 7 = 1....

Let $\Sigma=\{a, b, c\}$. For $x \in \Sigma^{\star}$, and $\alpha \in \Sigma$, let $\#_\alpha(x)$ denote the number of occurrences of a in $x$. Which one or more of the following o...

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

Consider the two lists List-I and List-II given below: List - I List - II (i) Context free languages (a) Closed under union (ii) Recursive languages (b) Not closed under complement...

Let $L_1, L_2$ be two regular languages and $L_3$ a language which is not regular. Which of the following statements is/are always TRUE?

Let $L_1, L_2$ be two regular languages and $L_3$ a language which is not regular. Which of the following statements is/are always TRUE?

Which of the following statements is/are CORRECT?

Consider the following languages: L 1 = {a n wa n | w $$\in$$ {a, b}*} L 2 = {wxw R | w, x $$\in$$ {a, b}*, | w | , | x | > 0} Note that w R is the reversal of the string w. Which...

Let L 1 be a regular language and L 2 be a context-free language. Which of the following languages is/are context-free?

Consider the following two statements about regular languages: S 1 : Every infinite regular language contains an undecidable language as a subset. S 2 : Every finite language is re...

Suppose that L 1 is a regular and L 2 is a context-free language, Which one of the following languages is NOT necessarily context-free?

Let L ⊆ {0,1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k s...

Consider the following statements. I. If L 1 $$ \cup $$ L 2 is regular, then both L 1 and L 2 must be regular. II. The class of regular languages is closed under infinite union. Wh...

For Σ = {a, b}, let us consider the regular language L = {x | x = a 2+3k or x = b 10+12k , k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by th...

If L is a regular language over Σ = {a, b}, which one of the following languages is NOT regular?

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT? I. L₁ U L₂ is context-free. II. L₁ is context-free. III. L₁...

Consider the following two statements : $$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,$$ If all states of an $$NFA$$ are accepting states then the language accepted by the $$\,\,\,\,\,\,\,\,\,...

Which of the following languages is/are regular? $${L_1}:\left\{ {wx{w^R}|w,x\, \in \left\{ {a,b} \right\}{}^ * } \right.$$ and $$\left. {\left| w \right|,\left| x \right| > 0} \ri...

Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$\left. \, \right\}$$. Let $${L_...

Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$\left. \, \right\}$$. Let $${L_...

Which one of the following is TRUE?

If $${L_1} = \left\{ {{a^n}\left| {n \ge \left. 0 \right\}} \right.} \right.$$ and $${L_2} = \left\{ {{b^n}\left| {n \ge \left. 0 \right\}} \right.} \right.,$$ consider $$\left. {\...

Consider the languages $${L_1} = \phi $$ and $${L_2} = \left\{ a \right\}.$$ Which one of the following represents $${L_1}\,L_2^ * UL_1^ * ?$$

Consider the following languages $${L_1} = \left\{ {{0^p}{1^q}{0^r}\left| {p,q,r \ge 0} \right.} \right\}$$ $${L_2} = \left\{ {{0^p}{1^q}{0^r}\left| {p,q,r \ge 0,p \ne r} \right.}...

The lexical analysis for a modern computer language such as java needs the power of which one of the following machine model in a necessary and sufficient sense?

Which of the following are decidable? $$1.$$ Whether the intersection of two regular languages is infinite $$2.$$ Whether a given context-free language is regular $$3.$$ Whether tw...

A minimum state deterministic finite automation accepting the language $$L = \left\{ {w\left| {w \in } \right.\,\,{{\left\{ {0,1} \right\}}^ * },\,\,} \right.$$ number of $$0'$$s a...

Which of the following languages is regular?

If $$s$$ is a string over $${\left( {0 + 1} \right)^ * }$$ then let $${n_0}\left( s \right)$$ denote the number of $$0'$$ s in $$s$$ and $${n_1}\left( s \right)$$ the number of $$1...

Consider a $$DFA$$ over $$\sum { = \left\{ {a,\,\,b} \right\}} $$ accepting all strings which have number of $$a'$$s divisible by $$6$$ and number of $$b'$$s divisible by $$8$$. Wh...

Consider the following languages: $${L_1} = \left\{ {w\,w\left| {w \in {{\left\{ {a,\,b} \right\}}^ * }} \right.} \right\}$$ $${L_2} = \left\{ {w\,{w^R}\left| {w \in {{\left\{ {a,\...

Let $$L$$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite-state automaton accepting $$L$$ is

Which of the following statements is false?

Let $$L$$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite-state automation accepting $$L$$ is

Which of the following sets can be recognized by a Deterministic Finite-state Automation?

$$\sum { = \left\{ {a,b} \right\},\,\,} $$ which one of the following sets is not countable.

If $${L_1}$$ and $${L_2}$$ are context free languages and $$R$$ a regular set, one of the languages below is not necessarily a context free language. Which one?

Let $$L \subseteq \sum {^{^ * }\,} $$ where $$\,\sum { = \,\,\left\{ {a,b} \right\}\,\,} $$ which of the following is true?

Given that language $${L_1}$$ is regular and that the language $${L_1} \cap {L_2}$$ is regular is the language $${L_2}$$ is always regular?

Which of the following statements is / are true / false? Regular languages are closed under infinite union.

Which of the following statements is / are true / false? The language $$\left\{ {{0^n}\,\left| {\,n} \right.} \right.$$ is prime$$\left. \, \right\}$$ is not regular

State whether the following statement is TRUE / FALSE. Regularity is preserved under the operation of string reversal.

Context free languages and regular languages are both closed under the operation(s) of :