Finite Automata and Regular Language · Theory of Computation · GATE CSE

Which one of the following regular expressions correctly represents the language of the finite automation given below? ...

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

Consider the following statements. I. If L1 $$ \cup $$ L2 is regular, then both L1 and L2 must be regular. II. The class of regular languages is close...

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 = a2+3k or x = b10+12k, k ≥ 0}. Which one of the following can be a pumping length (th...

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

Language $${L_1}$$ is defined by the grammar: $$S{}_1 \to a{S_1}b|\varepsilon $$ Language $${L_2}$$ is defined by the grammar: $$S{}_2 \to ab{S_2}|\va...

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

Let $$L$$ be the language represented by the regular expression $$\sum {^ * 0011\sum {^ * } } $$ where $$\sum { = \left\{ {0,1} \right\}} .$$ What is ...

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.} \...

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

Which one of the following is TRUE?

Consider the finite automation in the following figure. What is the set of reachable states for the input string $$0011?$$...

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

What is the complement of the language accepted by the $$NFA$$ shown below? Assume $$\sum { = \left\{ a \right\}\,\,} $$ and $$\varepsilon $$ is the ...

Let $${L_1}$$ recursive language. Let $${L_2}$$ and $${L_3}$$ be languages that are recursively enumerable but not recursive. Which of the following s...

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

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

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

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

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

Let $$L$$ denote the language generated by the grammar $$S \to 0S\left. 0 \right|00.$$ Which one of the following is true?

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

If the regular set $$A$$ is represented by $$A = {\left( {01 + 1} \right)^ * }$$ and the regular set $$'B'$$ is represented by $$B = \left( {{{\left( ...

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

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

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

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

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

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

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

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\} $...

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

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

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

Given a language $$𝐿,$$ define $${L^i}$$ as follows: $${L^0} = \left\{ \varepsilon \right\}$$ $${L^i} = {L^{i - 1}}.\,\,L$$ for all $$i > 0$$ ...

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

Consider the following languages: $$$\eqalign{ & {L_1} = \left\{ {{a^n}{b^m}{c^{n + m}}:m,n \ge 1} \right\} \cr & {L_2} = \left\{ {{a^n...

Consider the transition diagram of a $$PDA$$ given below with input alphabet $$\sum {\, = \left\{ {a,b} \right\}} $$ and stack alphabet $$\Gamma = \l...

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

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 \ri...

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

Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is___________....

Consider the NPDA $$\left\langle {Q = \left\{ {{q_0},{q_1},{q_2}} \right\}} \right.,$$ $$\Sigma = \left \{ 0, 1 \right \},$$ $$\Gamma = \left \{ 0, 1,...

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

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

Which of the regular expression given below represent the following $$DFA?$$ ...

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

Consider the set of strings on $$\left\{ {0,1} \right\}$$ in which, every substring of $$3$$ symbols has at most two zeros. For example, $$001110$$ an...

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

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

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

$$L = {L_1} \cap {L_2}$$ where $${L_1}$$ and $${L_2}$$ are languages defined as follows. $${L_1} = \left\{ {{a^m}{b^m}\,c\,{a^n}{b^n}\left| {m,n \ge...

The above $$DFA$$ accepts the set of all strings over $$\left\{ {0,\,\,1} \right\}$$ that...

Given below are two finite state automata ($$ \to $$ indicates the start state and $$F$$ indicates a final state) Which of the following represen...

Match the following $$NFAs$$ with the regular expressions they correspond to ...

Which of the following are regular sets? ...

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

Which of the following languages is regular?

Consider the following finite state automation The language accepted by this automation is given by the regular expression...

Consider the following finite state automation The minimum state automation equivalent to the above $$FSA$$ has the following number of states...

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

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

Consider the machine $$M:$$ The language recognized by $$M$$ is: ...

The following finite state machine accepts all those binary strings in which the number of $$1's$$ and $$0's$$ are respectively ...

Consider the $$NFA$$ $$M$$ shown below. Let the language accepted by $$M$$ be $$L.$$ Let $${L_1}$$ be the language accepted by the $$NFA$$, $${M_1}$...

Consider the following deterministic finite state automation $$M.$$ Let $$S$$ denote the set of seven bit binary strings in which the first, the fo...

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

The Finite state machine described by the following state diagram with $$A$$ as starting state, where an arc label is $$x/y$$ and $$x$$ stands for $$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 ...

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

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

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

Which one of the following regular expressions over $$\left\{ {0,\,\,1} \right\}$$ denotes the set of all strings not containing $$100$$ as substring?

A finite state machine with the following state table has a single input $$X$$ and a single out $$Z$$. If the initial state is unknown, then the sh...

Which of the following definitions below generates the same language as $$L$$ Where $$L = {\left\{ x \right.^n}{y^n}\left| {n \ge \left. 1 \right\}} ...

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

The regular expression for the language recognized by the finite state automation of is _________. ...

Which of the following regular expression identities are true?

If $$G$$ is a context-free grammar and $$w$$ is a string of length $$n$$ in $$L(G),$$ how long is a derivation of $$w$$ in $$G,$$ if $$G$$ is Chomsky ...

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?

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

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

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?

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