Question 1

Let L₁ = {w ? {0,1}? | w has at least as many occurrences of (110)'s as (011)'s}. Let L₂ = { ? {0,1}? | w has at least as many occurrences of (000)'s as (111)'s}. Which one of the following is TRUE? A) L₁ is regular but not L₂ B)L₂ is regular but not L₁ C)Both L₁ and L₂ are regular D)Neither L₁ nor L₂ are regular

Accepted Answer

B

Question 2

A spanning tree for a simple graph of order 24 has
A)12 edges
B)6 edges
C)23 edges
D)None of above.

Accepted Answer

A spanning tree of a graph is a subgraph that includes all the vertices of the original graph and is a tree. A tree with $n$ vertices always has $n-1$ edges. Therefore, a spanning tree for a graph of order 24 (meaning it has 24 vertices) must have $24-1 = 23$ edges.

Question 3

If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is
A)3
B)4
C)6
D)5

Accepted Answer

A 3-regular graph means every vertex has a degree of 3. Since the graph is planar and every region is bounded by 3 edges, we can use Euler's formula for planar graphs, V - E + F = 2, where V is the number of vertices, E is the number of edges, and F is the number of faces. Each edge contributes to 2 degrees (since it connects two vertices), so the sum of all degrees is 2E. For a 3-regular graph, this sum is also 3V. Therefore, 3V = 2E. Each face is bounded by 3 edges, but each edge is counted twice (once for each adjacent face), so 3F = 2E. Substituting F from Euler's formula (F = E - V + 2) into 3F = 2E gives 3(E - V + 2) = 2E, simplifying to E = 3V - 6. Substituting E = 3V/2 from 3V = 2E into E = 3V - 6 gives 3V/2 = 3V - 6, leading to V = 12 and E = 18. However, this detailed calculation is unnecessary for the given options, as the correct approach involves directly applying the constraints and realizing a mistake in the detailed explanation. The correct reasoning involves using Euler's formula and the given conditions to deduce the correct number of edges without needing to solve for V explicitly.

Question 4

If G is a connected planar graph of v vertices e edges and r regions then
A)v-e+r=2
B)e-v+r=2
C)v+e-r=2
D)None of above.

Accepted Answer

Euler's formula for a connected planar graph states that v - e + r = 2, where v is the number of vertices, e is the number of edges, and r is the number of regions.

Question 5

A Hamiltonian cycle in a Hamiltonian graph of order 24 has
A)12 edges.
B)24 edges
C)23 edges
D)None of above.

Accepted Answer

A Hamiltonian cycle in a graph is a cycle that visits each vertex exactly once and returns to the starting vertex. Therefore, in a graph of order 24 (meaning it has 24 vertices), a Hamiltonian cycle would have 24 edges, one for each vertex.

Question 6

If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is
A)3
B)4
C)6
D)5

Accepted Answer

A 3-regular graph means every vertex has a degree of 3. Since the graph is planar and every region is bounded by 3 edges, we can use Euler's formula for planar graphs, $V - E + F = 2$, where $V$ is the number of vertices, $E$ is the number of edges, and $F$ is the number of faces (regions). Each edge contributes to 2 regions since the graph is simple and planar. Therefore, $3F = 2E$, because each face is bounded by 3 edges but each edge is counted twice, once for each of its two adjacent faces. Substituting $F = \frac{2E}{3}$ into Euler's formula gives $V - E + \frac{2E}{3} = 2$, simplifying to $V = \frac{E}{3} + 2$. Since the graph is 3-regular, $3V = 2E$. Substituting $V = \frac{E}{3} + 2$ into $3V = 2E$ gives $E = 6$.

Question 7

The following grammar
G = (N, T, P, S)
N = {S, A, B}
T = {a, b, c}
P : S ? aSa
S ? aAa
A ? bB
B ? bB
B ? c is
A)is type 3
B)is type 2 but not type 3
C)is type 1 but not type 2
D)is type 0 but not type 1

Accepted Answer

This grammar is type 2 but not type 3 because it includes productions that have nonterminals on both sides of the production rule (e.g., S → aSa), which is allowed in context-free grammars (type 2) but not in regular grammars (type 3). It does not fit the criteria for type 1 (context-sensitive) or type 0 (unrestricted) as it does not require or allow for context in its production rules, nor does it include productions that would make it unrestricted.

Question 8

The following grammar
G = (N, T, P, S)
N = {S, A, B, C, D, E}
T = {a, b, c}
P : S ? aAB
AB ? CD
CD ? CE
C ? aC
C ? b
BE ? bc is
A)is type 3
B)is type 2 but not type 3
C)is type 1 but not type 2
D)is type 0 but not type 1

Accepted Answer

The answer of The following grammar
G = (N, T, P,...

Question 9

The following grammar
G = (N, T, P, S)
N = {S, A, B, C}
T = {a, b, c}
P : S ? aS
A ? bB
B ? cC
C ? a is
A)is type 3
B)is type 2 but not type 3
C)is type 1 but not type 2
D)is type 0 but not type 1

Accepted Answer

The given grammar is type 3 because all its production rules follow the form of either A → aB or A → a, where A and B are non-terminal symbols and a is a terminal symbol. This is characteristic of regular grammars, which are type 3 in the Chomsky hierarchy.

Question 10

P, Q, R are three languages. If P & R are regular and if PQ=R, then
A)Q has to be regular
B)Q cannot be regular
C)Q need not be regular
D)Q has to be a CFL

Accepted Answer

Q need not necessarily be regular. The operation described does not guarantee that Q will inherit the regularity property from P and R. For instance, if P is a regular language that accepts all strings and R is also a regular language, Q could be any language (including non-regular ones) that satisfies the equation PQ = R, depending on the specific languages P and R.

Question 11

Which of the following is true with respect to Kleene's theorem?
1 A regular language is accepted by a finite automaton.
2 Every language is accepted by a finite automaton or a turingmachine.
A)1 only
B)2 only
C)Both 1 and 2 are true statements
D)None is true

Accepted Answer

Kleene's theorem states that every regular language is accepted by a finite automaton and every language is accepted by a finite automaton or a Turing machine.

Question 12

Automaton accepting the regular expression of any number of a ' s is:
A)a*
B)ab*
C)(a/b)*
D)a*b*c

Accepted Answer

The regular expression "a*" represents any number of 'a's, including zero.

Question 13

Grammars that can be translated to DFAs:
A)Left linear grammar
B)Right linear grammar
C)Generic grammar
D)All of these

Accepted Answer

Right linear grammars can be directly translated to deterministic finite automata (DFAs) as they generate regular languages.

Question 14

Two strings x and y are indistinguishable if:
A)?*(s, x) = ?* (s, y), i.e. the state reached by a DFA M on input x is the same as the state reached by M on input y
B)if for every string z ? ?* either both xz and yz are in language A on ?* or both xz and yz are not in A
C)Both above statements are true
D)None of the above

Accepted Answer

Both statements A and B correctly define conditions under which two strings x and y are considered indistinguishable. Statement A describes indistinguishability in terms of reaching the same state in a DFA for both strings, while statement B describes it in terms of both strings, when concatenated with any string z, either both being in or both being out of a language A. These are two perspectives on the concept of indistinguishability in formal language theory and automata.

Question 15

Given an arbitrary non-deterministic finite automaton NFA with N states, the maximum number of states in an equivalent minimized DFA is at least: A)N² B)2^N C)2N D)N!

Accepted Answer

The answer of Given an arbitrary non-deterministic finite automaton NFA...

Question 16

Regular expressions are
A)Type 0 language
B)Type 1 language
C)Type 2 language
D)Type 3 language

Accepted Answer

Regular expressions are Type 0 language because they can generate any language that a Turing machine can recognize.

Question 17

The regular expression 0*(10)* denotes the same set as
A)(1*0)*1*
B)0+(0+10)*
C)(0+1)*10(0+1)*
D)None of the above

Accepted Answer

The regular expression 0*(10)* represents strings with zero or more '0's followed by zero or more repetitions of '10'. The expression 0+(0+10)* also represents strings starting with one or more '0's followed by any combination of '0's and '10's, which is equivalent.

Question 18

Consider the NFA M shown below. Let the language accepted by M be L. Let L₁ be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true? A) L₁ = {0,1}* ? L B) L₁ = {0,1}* C) L₁ is a subset of L D) L₁ = L

Accepted Answer

The answer of Consider the NFA M shown below.
 Let...

Question 19

Which of the statements is true:
A)The complement of a regular language is always regular.
B)Homomorphism of a regular language is always regular.
C)Both of the above are true statements
D)None of the above

Accepted Answer

Both statements A and B are true. The complement of a regular language is regular because regular languages are closed under complementation. Similarly, regular languages are closed under homomorphism, meaning the homomorphism of a regular language is always regular.

Question 20

The regular sets are closed under:
A)Union
B)Concatenation
C)Kleene closure
D)All of the above

Accepted Answer

Regular sets are closed under union, concatenation, and Kleene closure, meaning that if you perform any of these operations on regular sets, the result will also be a regular set.

Quiz 1: Formal Languages and Automata Theory: Part A

Let L₁ = {w ? {0,1}? | w has at least as many occurrences of (110) 's as (011) 's}. Let L₂ = { ? {0,1}? | w has at least as many occurrences of (000) 's as (111) 's}. Which one of the following is TRUE?

A spanning tree for a simple graph of order 24 has

If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is

If G is a connected planar graph of v vertices e edges and r regions then

A Hamiltonian cycle in a Hamiltonian graph of order 24 has

If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is

The following grammar G = (N, T, P, S) N = {S, A, B} T = {a, b, c} P : S ? aSa S ? aAa A ? bB B ? bB B ? c is

The following grammar G = (N, T, P, S) N = {S, A, B, C, D, E} T = {a, b, c} P : S ? aAB AB ? CD CD ? CE C ? aC C ? b BE ? bc is

The following grammar G = (N, T, P, S) N = {S, A, B, C} T = {a, b, c} P : S ? aS A ? bB B ? cC C ? a is

P, Q, R are three languages. If P & R are regular and if PQ=R, then

Which of the following is true with respect to Kleene's theorem? 1 A regular language is accepted by a finite automaton. 2 Every language is accepted by a finite automaton or a turingmachine.

Automaton accepting the regular expression of any number of a ' s is:

Grammars that can be translated to DFAs:

Two strings x and y are indistinguishable if:

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

Regular expressions are

The regular expression 0(10) denotes the same set as

Consider the NFA M shown below. Let the language accepted by M be L. Let L₁ be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

Which of the statements is true:

The regular sets are closed under:

Quiz 1: Formal Languages and Automata Theory: Part A

Let L1 = {w ? {0,1}? | w has at least as many occurrences of (110) 's as (011) 's}. Let L2 = { ? {0,1}? | w has at least as many occurrences of (000) 's as (111) 's}. Which one of the following is TRUE?

A spanning tree for a simple graph of order 24 has

If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is

If G is a connected planar graph of v vertices e edges and r regions then

A Hamiltonian cycle in a Hamiltonian graph of order 24 has

If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is

The following grammar G = (N, T, P, S) N = {S, A, B} T = {a, b, c} P : S ? aSa S ? aAa A ? bB B ? bB B ? c is

The following grammar G = (N, T, P, S) N = {S, A, B, C, D, E} T = {a, b, c} P : S ? aAB AB ? CD CD ? CE C ? aC C ? b BE ? bc is

The following grammar G = (N, T, P, S) N = {S, A, B, C} T = {a, b, c} P : S ? aS A ? bB B ? cC C ? a is

P, Q, R are three languages. If P & R are regular and if PQ=R, then

Which of the following is true with respect to Kleene's theorem? 1 A regular language is accepted by a finite automaton. 2 Every language is accepted by a finite automaton or a turingmachine.

Automaton accepting the regular expression of any number of a ' s is:

Grammars that can be translated to DFAs:

Two strings x and y are indistinguishable if:

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

Regular expressions are

The regular expression 0*(10) * denotes the same set as

Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

Which of the statements is true:

The regular sets are closed under:

Let L₁ = {w ? {0,1}? | w has at least as many occurrences of (110) 's as (011) 's}. Let L₂ = { ? {0,1}? | w has at least as many occurrences of (000) 's as (111) 's}. Which one of the following is TRUE?

The regular expression 0(10) denotes the same set as

Consider the NFA M shown below. Let the language accepted by M be L. Let L₁ be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?