Question 1

Let L={w \in (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?
A)(0*10*1)*
B)0*(10*10*)*
C)0*(10*1*)*0*
D)0*1(10*1)*10*

Accepted Answer

B) 0*(10*10*)* correctly represents the set L because it allows for any number of 0s at the beginning, followed by pairs of 1s separated by any number of 0s, ensuring an even number of 1s in any accepted string.

Question 2

Consider the languagesL₁={0^{i}1^{j}|i != j},L₂={0^{i}1^{j}|i = j},L₃ = {0^{i}1^{j}|i = 2j+1},L4 = {0^{i}1^{j}|i != 2j}.Which one of the following statements is true? A)Only L₂ is context free B)Only L₂ and L₃ are context free C)Only L₁ and L₂ are context free D)All are context free

Accepted Answer

D

Question 3

Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
A)n-1
B)n
C)n+1
D)2n-1

Accepted Answer

A non-deterministic finite automaton (NFA) that accepts all substrings of a string of length n can be constructed with n+1 states. This is because you need a state for each position in the string (including the start and end positions) to potentially start and end a substring, thus requiring n+1 states.

Question 4

Let L = L₁ \cap L₂, where L₁ and L₂ are languages as defined below: L₁ = {a^{m}b^{m}ca^{n}b^{n} | m, n >= 0 } L₂ = {a^{i}b^{j}c^{k} | i, j, k >= 0 } Then L is A)Not recursive B)Regular C)Context free but not regular D)Recursively enumerable but not context free.

Accepted Answer

The language L = L₁ ∩ L₂ is context-free but not regular. This is because L is the intersection of two languages, where L₁ = {a^m b^m ca^n b^n | m, n >= 0} is a context-free language that requires a matching number of a's and b's both before and after a 'c', which cannot be recognized by a finite automaton, making it non-regular. L₂ = {a^i b^j c^k | i, j, k >= 0} is a regular language as it can be recognized by a finite automaton (it does not require matching numbers of symbols). The intersection of a context-free language and a regular language is context-free, thus making L context-free. However, since L requires a specific pattern that cannot be recognized by a finite automaton (due to the need to match numbers of a's and b's), it is not regular.

Question 5

Consider the language L₁,L₂,L₃ as given below. L₁={0^{p}1^{q} | p,q \in N} L₂={0^{p}1^{q} | p,q \in N and p=q} L₃={0^{p}1^{q}1^{r} | p,q,r \in N and p=q=r} Which of the following statements is NOT TRUE? A)Push Down Automata (PDA) can be used to recognize L₁ and L₂ B)L₁ is a regular language C)All the three languages are context free D)Turing machine can be used to recognize all the three languages

Accepted Answer

The answer of Consider the language L₁,L₂,L₃ as given below. L₁={0^{p}1^{q}...

Question 6

Definition of a language L with alphabet {a} is given as following. L= { a^{nk} | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?
A)k+1
B)n+1
C)2^(n+1)
D)2^(k+1)

Accepted Answer

The minimum number of states needed in a DFA to recognize the language L is n+1. This is because the DFA needs to be able to distinguish between all strings of length multiple of n (a^n, a^2n, a^3n, ...) and those that are not. To do this, it cycles through n states for each segment of n 'a's and returns to the initial state after counting n 'a's, requiring a total of n+1 states (n states for the cycle and 1 additional state to handle the acceptance condition).

Question 7

Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is a context-free language, then is L' (complement of L) also context-free?
3) If L is a regular language, then is L' also regular?
4) If L is a recursive language, then, is L' also recursive?
A)1, 2, 3, 4
B)1, 2
C)2, 3, 4
D)3, 4

Accepted Answer

3) The problem of determining if the complement of a regular language is regular is decidable because regular languages are closed under complementation. 4) The problem of determining if the complement of a recursive language is recursive is decidable because recursive languages are closed under complementation.

Question 8

Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For examples, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are

A) $\begin{array}{|c|c|c|c|c|c|}
\hline & 00 & 01 & 10 & 11 & Q \
\hline 00 & 1 & 0 & & & \
\hline 01 & & & & 1 & \
\hline 10 & 0 & & & & \
\hline 11 & & & 0 & & \
\hline
\end{array}$

B) $\begin{array}{|c|c|c|c|c|c|}
\hline & 00 & 01 & 10 & 11 & \mathrm{Q} \
\hline 00 & & 0 & & & 1 \
\hline 01 & & 1 & & & \
\hline 10 & & & & 0 & \
\hline 11 & & 0 & & & \
\hline
\end{array}$

C) $\begin{array}{|c|c|c|c|c|c|}
\hline & 00 & 01 & 10 & 11 & \mathrm{Q} \
\hline 00 & & 1 & & & 0 \
\hline 01 & & 1 & & & \
\hline 10 & & & 0 & & \
\hline 11 & & 0 & & & \
\hline
\end{array}$

D) $\begin{array}{|c|c|c|c|c|c|}
\hline & 00 & 01 & 10 & 11 & \mathrm{Q} \
\hline 00 & & 1 & & & 0 \
\hline 01 & & & & 1 & \
\hline 10 & 0 & & & & \
\hline 11 & & & 0 & & \
\hline
\end{array}$

Accepted Answer

The answer of Consider the set of strings on {0,1}...

Question 9

Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression
A)b*ab*ab*ab
B)(a+b)*
C)b*a(a+b)*
D)b*ab*ab

Accepted Answer

The automaton accepts strings that start with any number of b's, followed by an a, followed by any number of a's or b's. This is represented by the regular expression b*a(a+b)*.

Question 10

The minimum state automaton equivalent to the above FSA has the following number of states
A)1
B)2
C)3
D)4

Accepted Answer

The minimum state automaton equivalent to a given finite state automaton (FSA) can be determined through a process called state minimization. This process involves identifying and merging equivalent states (states that cannot be distinguished by any input sequence). Without the specific details of the FSA provided, it's impossible to accurately determine the exact number of states in its minimal equivalent. However, the question seems to imply a context where the answer is known, and based on common examples and principles of state minimization, a 2-state automaton is a common result for simple FSAs that can't be reduced to a single state but can be simplified from more complex forms.

Question 11

Which of the following languages is regular?
A){WW^R | W € {0,1}+ }
B){WW^R X | X W € {0,1}+ }
C){WW^R | X W € {0,1}+ }
D){XWW^R | X W € {0,1}+ }

Accepted Answer

The answer of Which of the following languages is regular?
A){WW^R...

Question 12

The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,2) is
A)not recurcise
B)is recursive and deterministic CFL
C)is a regular language
D)is not a deterministic CFL but a CFL

Accepted Answer

The language L = { 0^i 2 1^i | i ≥ 0 } is a deterministic context-free language (CFL) because it can be recognized by a deterministic pushdown automaton (PDA). The PDA can push a symbol onto the stack for each 0 it reads, and then for each 1 it reads, it can pop a symbol off the stack, ensuring that the number of 0s and 1s are equal. The presence of the 2 in the middle serves as a deterministic point to switch from pushing to popping, which makes the language deterministic.

Question 13

A minimum state deterministic finite automation accepting the language L = {W |W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has
A)15 States
B)11 states
C)10 states
D)9 states

Accepted Answer

To construct a minimum state deterministic finite automaton (DFA) for the given language, we need to consider the divisibility by both 3 and 5. For divisibility by 3, we need 3 states (to count the number of 0's modulo 3), and for divisibility by 5, we need 5 states (to count the number of 1's modulo 5). Since we need to track both conditions simultaneously, we multiply the number of states needed for each condition, resulting in 3 * 5 = 15 states.

Question 14

If s is a string over (0 + 1)* then let n0 (s) denote the number of 0's in s and n₁ (s)the number of l's in s. Which one of the following languages is not regular? A)L = {s € (0 + 1)*n0 (s) is a 3-digit prime B)L = {s € (0 + 1)* | for every prefix s' of s, l 0 (s') - n₁ (s') | <= 2 } C)L={s € (0+1)* | n0(s) - n₁(s) | <= 4} D)L = {s € (0 + 1) | n0 (s) mod 7 = n₁ (s) mod 5 = 0 }

Accepted Answer

The answer of If s is a string over (0...

Question 15

For S € (0+1)* let d(s)denote the decimal value of s(e.g.d(101)= 5).Let L = {s € (0 + 1) | d (s) mod 5 = 2 and d (s) mod 7 != 4)}Which one of the following statements is true?
A)L is recursively enumerable, but not recursive
B)L is recursive, but not context-free
C)L is context-free, but not regular
D)L is regular

Accepted Answer

The language L is defined by two conditions based on the decimal value of a binary string: it must leave a remainder of 2 when divided by 5, and it must not leave a remainder of 4 when divided by 7. However, the condition that a number must leave a remainder of 2 when divided by 5 can be represented by a finite automaton, as the set of such numbers is periodic with a period of 5. Similarly, the condition that a number must not leave a remainder of 4 when divided by 7 does not affect the regularity of the language, as excluding a specific remainder out of 7 possible outcomes can also be represented with a finite automaton. Therefore, the combination of these conditions still results in a language that can be recognized by a finite automaton, making L a regular language.

Question 16

Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
A)Both DHAM3 and SHAM3 are NP-hard
B)SHAM3 is NP-hard, but DHAM3 is not
C)DHAM3 is NP-hard, but SHAM3 is not
D)Neither DHAM3 nor SHAM3 is NP-hard

Accepted Answer

Both DHAM3 and SHAM3 are NP-hard because determining if a Hamiltonian cycle exists (DHAM3) is a well-known NP-hard problem, and finding such a cycle (SHAM3) is at least as hard, if not harder, than merely determining its existence.

Question 17

Consider the following statements about the context free grammarG = {S - >SS, S - >ab, S - >ba, S - ?}I. G is ambiguousII. G produces all strings with equal number of a's and b'sIII. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G?
A)1 only
B)1 and 3
C)2 and 3
D)1,2 and 3

Accepted Answer

The answer of Consider the following statements about the context...

Question 18

Let L₁ be a regular language, L₂ be a deterministic context-free language and L₃ a recursively enumerable, but not recursive, language. Which one of the following statements is false? A)L₁ n L₂ is a deterministic CFL B)L₃ n L₁ is recursive C)L₁ U L₂ is context free D)L₁ n L₂ n L₃ is recursively enumerable

Accepted Answer

The intersection of a recursively enumerable language that is not recursive with a regular language does not guarantee a recursive language, making statement B false.

Question 19

Consider the regular language L =(111+11111)*. The minimum number of states
A)3
B)5
C)8
D)9

Accepted Answer

The answer of Consider the regular language L =(111+11111)*. The...

Question 20

Consider the languages: GATE[2005]L₁ = {wwR w €{0, 1} *1L₂ ={w#ww € {O,1}*},where # is a special symbolL₃ ={www € {0,1}*}Which one of the following is TRUE? A)L₁ is a deterministic CFL B)L₂ is a deterministic CFL C)L₃ is a CFL, but not a deterministic CFL D)L₃ is a deterministic CFL

Accepted Answer

The answer of Consider the languages: GATE[2005]L₁ = {wwR w...

Quiz 1: Formal Languages and Automata Theory: Part A

Let L={w \in (0 + 1) *|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

Consider the languagesL₁={0^{i}1^{j}|i != j},L₂={0^{i}1^{j}|i = j},L₃ = {0^{i}1^{j}|i = 2j+1},L4 = {0^{i}1^{j}|i != 2j}.Which one of the following statements is true?

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

Let L = L₁ \cap L₂, where L₁ and L₂ are languages as defined below: L₁ = {a^{m}b^{m}ca^{n}b^{n} | m, n >= 0 } L₂ = {a^{i}b^{j}c^{k} | i, j, k >= 0 } Then L is

Consider the language L₁,L₂,L₃ as given below. L₁={0^{p}1^{q} | p,q \in N} L₂={0^{p}1^{q} | p,q \in N and p=q} L₃={0^{p}1^{q}1^{r} | p,q,r \in N and p=q=r} Which of the following statements is NOT TRUE?

Definition of a language L with alphabet {a} is given as following. L= { a^{nk} | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?

Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then is L' (complement of L) also context-free? 3) If L is a regular language, then is L' also regular? 4) If L is a recursive language, then, is L' also recursive?

Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression

The minimum state automaton equivalent to the above FSA has the following number of states

Which of the following languages is regular?

The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,2) is

A minimum state deterministic finite automation accepting the language L = {W |W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has

If s is a string over (0 + 1) * then let n0 (s) denote the number of 0's in s and n₁ (s) the number of l's in s. Which one of the following languages is not regular?

For S € (0+1) * let d(s) denote the decimal value of s(e.g.d(101) = 5) .Let L = {s € (0 + 1) | d (s) mod 5 = 2 and d (s) mod 7 != 4) }Which one of the following statements is true?

Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E) with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

Consider the following statements about the context free grammarG = {S - >SS, S - >ab, S - >ba, S - ?}I. G is ambiguousII. G produces all strings with equal number of a's and b'sIII. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G?

Let L₁ be a regular language, L₂ be a deterministic context-free language and L₃ a recursively enumerable, but not recursive, language. Which one of the following statements is false?

Consider the regular language L =(111+11111) *. The minimum number of states

Consider the languages: GATE[2005]L₁ = {wwR w €{0, 1} 1L₂ ={w#ww € {O,1}},where # is a special symbolL₃ ={www € {0,1}*}Which one of the following is TRUE?