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?

Let $M$ be a non-deterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) that is equiva...

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 complementation (iii) Regular languages (c) Closed...

Let $\Sigma=\{1,2,3,4\}$ For $x \in \Sigma^*$, let prod $(x)$ be the product of symbols in $x$ modulo 7 . We take $\operatorname{prod}(\varepsilon)=1$, where $\varepsilon$ is the null string. For example, $\operatorname{...

A regular language $L$ is accepted by a non-deterministic finite automaton (NFA) with $n$ states. Which of the following statement(s) is/are FALSE?

Consider a finite state machine (FSM) with one input $X$ and one output $f$, represented by the given state transition table. The minimum number of states required to realize this FSM is ________ . (Answer in integer) Pr...

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 option(s) define(s) regular language(s)?

Consider the following two regular expressions over the alphabet {0,1} : $$r = 0^* + 1^*$$ $$s = 01^* + 10^*$$ The total number of strings of length less than or equal to 5, which are neither in r nor in s , is ________

Let L 1 be the language represented by the regular expression b * ab * (ab * ab * ) * and L 2 = { w ∈ (a + b) * | |w| ≤ 4 } , where |w| denotes the length of string w . The number of strings in L 2 which are also in L 1...

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?

Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: $$\mathrm{letter\to[A-Za-z]}$$ $$\mathrm{letter\to[0-9]}$$ $$\mathrm{id\to letter(l...

Consider the language L over the alphabet {0, 1}, given below: $$L = \{ w \in {\{ 0,1\} ^ * }|w$$ does not contain three or more consecutive $$1's\} $$. The minimum number of states in a Deterministic Finite-State Automa...

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 of the following is/are TRUE?

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 states?

Consider the following language. L = { w ∈ {0, 1}* | w ends with the substring 011} Which one of the following deterministic finite automata accepts L?

Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string ∈ divisible by three.

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?

Consider the following language. L = {x $$ \in $$ {a, b}* | number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ______.

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. Which of the above statements is/are TRUE...

Let $\Sigma$ be the set of all bijections from $\{1, \ldots, 5\}$ to $\{1, \ldots, 5\}$, where id denotes the identity function, i.e. $\operatorname{id}(j)=j, \forall j$. Let $\circ$ denote composition on functions. For...

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

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 the pumping lemma) for L?

Let $$N$$ be an $$NFA$$ with $$n$$ states. Let $$k$$ be the number of states of a minimal $$DFA$$ which is equivalent to $$N.$$ Which one of the following is necessarily true?

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

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive $$0s$$ and two consecutive $$1s?$$

The number of states in the minimum sized $$DFA$$ that accepts the language defined by the regular expression $$${\left( {0 + 1} \right)^ * }\left( {0 + 1} \right){\left( {0 + 1} \right)^ * }$$$ is ___________________.

Consider the alphabet $$\sum { = \left\{ {0,1} \right\},} $$ the null/empty string $$\lambda $$ and the sets of strings $${X_0},\,{X_1},$$ and $${X_2}$$ generated by the corresponding non-terminals of a regular grammar....

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} \right\},\,{w^R}$$ is the reverse of string...

Let $$L$$ be the language represented by the regular expression $$\sum {^ * 0011\sum {^ * } } $$ where $$\sum { = \left\{ {0,1} \right\}} .$$ What is the minimum number of states in a $$DFA$$ that recognizes $$\overline...

The number of states in the minimal deterministic finite automaton corresponding to the regular expression $${\left( {0 + 1} \right)^{\,\, * }}\left( {10} \right)$$ is ________________.

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_2} = \left\{ {w \in \left\{ {0,\,\,1} \r...

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. {\rm I} \right)$$ $$\,\,\,{L_{1 \bullet }}...

The length of the shortest string NOT in the language (over $$\sum { = \left\{ {a,\,\,b} \right\}} $$) of the following regular expression is ____________. $$$a{}^ * b{}^ * \left( {ba} \right){}^ * a{}^ * $$$

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_2} = \left\{ {w \in \left\{ {0,\,\,1} \r...

Which one of the following is TRUE?

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

Given the language L= { ab, aa, baa }, which of the following strings are in L* ? 1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa

Definition of the language $$L$$ with alphabet $$\left\{ a \right\}$$ is given as following. $$L = \left\{ {{a^{nk}}} \right.\left| {k > 0,\,n} \right.$$ is a positive integer constant$$\left. \, \right\}$$ What is the m...

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?

Let $$L = \left\{ {w \in {{\left( {0 + 1} \right)}^ * }\left| {\,w} \right.} \right.$$ has even number of $$\,\left. {1's} \right\},$$ i.e $$L$$ is the set of all bit strings with even number of $$1's.$$ which one of rhe...

Let $$w$$ be any string of length $$n$$ in $${\left\{ {0,1} \right\}^ * }$$. Let $$L$$ be the set of all substrings of $$w.$$ What is the minimum number of states in a non-deterministic finite automation that accepts $$L...

Which one of the following languages over the alphabet $$\left\{ {0,\left. 1 \right)} \right.$$ is described by the regular expression $${\left( {0 + 1} \right)^ * }0{\left( {0 + 1} \right)^ * }0{\left( {0 + 1} \right)^...

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 and $$1'$$s in $$w$$ are divisible by $$3...

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'$$s in $$s.$$ Which one of the followin...

For $$s \in {\left( {0 + 1} \right)^ * },$$ let $$d(s)$$ denote the decimal value of $$s(e. g.d(101)=5)$$ Let $$L = \left\{ {s \in {{\left( {0 + 1} \right)}^ * }\left| {\,d\left( s \right)\,} \right.} \right.$$ mod $$5=2...

Consider the regular language $$L = {\left( {111 + 11111} \right)^ * }.$$ The minimum number of states in any $$DFA$$ accepting this language is

The regular expression $${0^ * }\left( {{{10}^ * }} \right){}^ * $$denotes the same set as

Consider the set $$\sum {^ * } $$ of all strings over the alphabet $$\,\sum { = \,\,\,\left\{ {0,\,\,\,1} \right\}.\sum {^ * } } $$ with the concatenation operator for strings

The smallest finite automaton which accepts the language $$L = \left. {\left\{ x \right.} \right|$$ length of $$x$$ is divisible by $$\left. 3 \right\}$$ has

Given an arbitrary non-deterministic finite automaton $$(NFA)$$ with $$N$$ states, the maximum number of states in an equivalent minimized $$DFA$$ is at least

Consider the following two statements; $${S_1}\,\,:\,\,\left\{ {{0^{2n}}\left| {n \ge 1} \right.} \right\}$$ is a regular language $${S_2}\,\,:\,\,\left\{ {{0^m}{1^n}{0^{m + n}}\left| {m \ge 1} \right.\,\,and\,\,n \ge \l...

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$$. What is the minimum number of states that...

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,\,b} \right\}}^ * },} \right.{w^R}\,\,} \...

What can be said about a regular language $$L$$ over $$\left\{ a \right\}$$ whose minimal finite state automation has two states?

Let $$S$$ and $$T$$ be languages over $$\sum { = \left\{ {a,b} \right\}} $$ represented by the regular expressions $${\left( {a + {b^ * }} \right)^ * }$$ and $$\,{\left( {a + b} \right)^ * },$$ respectively. Which of the...

Consider the regular expression $$(0+1)(0+1).......n$$ times. The minimum state finite automation that recognizes the language represented by this regular expression contains:

If the regular set $$A$$ is represented by $$A = {\left( {01 + 1} \right)^ * }$$ and the regular set $$'B'$$ is represented by $$B = \left( {{{\left( {01} \right)}^ * }{1^ * }} \right),$$ which of the following is true?

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

How many substrings of different lengths (non-zero) can be formed from a character string of length $$n$$ ?

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

Which of the following statements is false?

The string $$1101$$ does not belong to the set represented by

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 one of the following regular expressions over $$\left\{ {0,\,\,1} \right\}$$ denotes the set of all strings not containing $$100$$ as substring?

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

Which two of the following four regular expressions are equivalent? (i) $${\left( {00} \right)^ * }\left( {\varepsilon + 0} \right)$$ (ii) $${\left( {00} \right)^ * }$$ (iii) $${0^ * }$$ (iv) $$0\,\,{\left( {00} \right)^...

State True or False with one line explanation: A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits).

The number of sub-strings (of all lengths inclusive) that can be formed from a character string of length $$n$$ is

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? The language $$\left\{ {{0^n}\,\left| {\,n} \right.} \right.$$ is prime$$\left. \, \right\}$$ is not regular

Which of the following regular expression identities are true?

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

Let $$r = 1\,{\left( {1 + 0} \right)^ * },s = {11^ * }\,0$$ and $$\,t = {1^ * }\,0$$ be three regular expressions. Which one of the following is true?

Which one of the following is the strongest correct statement about a finite language over some finite alphabet $$\sum ? $$

State whether the following statement is TRUE / FALSE. All subjects of regular sets are regular.

Let $${R_1}$$ and $${R_2}$$ be regular sets defined over the alphabet $$\sum \, $$ then:

State whether the following statement is TRUE / FALSE. A minimal $$DFA$$ that is equivalent to an $$NFDA$$ with $$n$$ modes has always 2 n states

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

How many substrings (of all lengths inclusive ) can be formed from a character string of length $$n$$? Assume all characters to be distinct. Prove your answer.

Is the class of regular sets closed under infinite union? Explain.

Give the regular expression over $${\left\{ {0,\,\,1} \right\}}$$ to denote the set of proper non-null substrings of the string $$0110$$.

Give minimal $$DFA$$ that performs as a Mod-$$3$$ $$1's$$ counter, i.e., outputs a $$1$$ each time the number of $$1's$$ in the input sequence is a sequence is a multiple of $$3.$$