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

Prefix (L) = {x ϵ ∑* | ∃x ϵ ∑* such that xy ϵ L}

L . LR = {xy | x ϵ L, yR ϵ L}

Prefix (L) = {x ϵ ∑* | ∃x ϵ ∑* such that xy ϵ L}

Suffix (L) = {y ϵ ∑* | ∃x ϵ ∑* such that xy ϵ L}

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

\(\left\{ {{q_0},\;{q_1}} \right\}\)

\(\left\{ {{q_0},\;{q_1},\;{q_2}} \right\}\)

\(\left\{ {{q_0},\;{q_1}} \right\}\)

\(\left\{ {{q_0},\;{q_1},\;{q_2},\;{q_3}} \right\}\)

Match the following:P. Lexical analysis1. Graph coloringQ. Parsing2. DFA minimizationR. Register allocation3. Post-order traversalS. Expression evaluation4. Production tree

P – 2, Q – 3, R – 4, S - 1

P – 2, Q – 3, R – 1, S - 4

P – 2, Q – 1, R – 4, S - 3

P – 2, Q – 4, R – 1, S - 3

P – 2, Q – 3, R – 4, S - 1

Consider the following context-free grammars:G1 : S → aS|B, B → b|bBG2 : S → aA|bB, A → aA|B|ϵ, B → bB|ϵ Which one of the following pairs of languages is generated by G1 and G2, respectively?

{ambn|m > 0 or n > 0} and {ambn|m > 0 and n > 0}

{ambn|m > 0 and n > 0} and {ambn|m > 0 or n ≥ 0}

{ambn|m ≥ 0 or n > 0} and {ambn|m > 0 and n > 0}

{ambn|m ≥ 0 and n > 0} and {ambn|m > 0 or n > 0}

Pushdown automata are _____ machines augmented with additional memory in the form of a stack.

nondeterministic infinite state

Choose the correct statement —

The set B, consisting of all strings made up of only a’s and b’s having equal number of a’s and b’s defines a regular language

A = {an bn | n = 1, 2, 3, .... } is a regular language

The set B, consisting of all strings made up of only a’s and b’s having equal number of a’s and b’s defines a regular language

For Σ = {a,b} the regular expression r = (aa)*(bb)*b denotes

Set of strings with 2 a’s and 2 b’s

Set of strings with 2 a’s 2 b’s followed by b

Set of strings with 2 a’s followed by b’s which is a multiple of 3

Set of strings with even number of a’s followed by odd number of b’s

Pumping lemma for regular language is generally used for proving :

whether two given regular expressions are equivalent

40 + Mcqs in Regular Languages And Finite Automata in Computer Science Page 1 McqOptions

1.	Let L={w∈(0+1)∗∣w has even number of 1's}, i.e. L is the set of all bit strings with even number of 1's. Which one of the regular expression below represents L?
A.	\((0101)*\)
B.	\(0(1010)\)
C.	\(0(101)0*\)
D.	\(01(101)10\)
Answer» C. \(0(101)0*\)

Discussion

2.	If L is a regular language over Σ = {a, b}, which one of the following languages is NOT regular?
A.	L . LR = {xy \| x ϵ L, yR ϵ L}
B.	{wwR \| w ϵ L}
C.	Prefix (L) = {x ϵ ∑* \| ∃x ϵ ∑* such that xy ϵ L}
D.	Suffix (L) = {y ϵ ∑* \| ∃x ϵ ∑* such that xy ϵ L}
Answer» C. Prefix (L) = {x ϵ ∑* \| ∃x ϵ ∑* such that xy ϵ L}

Discussion

3.	In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?
A.	(L + D) *
B.	(L.D) *
C.	L(L + D) *
D.	L(L.D) *
Answer» D. L(L.D) *

Discussion

4.	Let 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?
A.	k ≥ 2n
B.	k ≥ n
C.	k ≤ n2
D.	k ≤ 2n
Answer» E.

Discussion

5.	Number of states in DFA accepting the following language is:L = { an b2m \| n, m ≥ 1 }
A.	n
B.	5
C.	m
D.	2
Answer» C. m

Discussion

6.	Consider the following two statements:I. If all states of an NFA are accepting states then the language accepted by the NFA is ∑*.II. There exists a regular language A such that for all languages B, A ∩ B is regular.Which one of the following is CORRECT?
A.	Only I is true
B.	Only II is true
C.	Both I and II are true
D.	Both I and II are false
Answer» C. Both I and II are true

Discussion

7.	Consider the DFA A given belowWhich of the following are FALSE?1. Complement of L(A) is context-free.2. L(A) = L((110 + 0)(0 + 1)01)3. For the language accepted by A, A is the minimal DFA.4. A accepts all strings over {0, 1} of length at least 2.
A.	1 and 3 only
B.	2 and 4 only
C.	2 and 3 only
D.	3 and 4 only
Answer» E.

Discussion

8.	Consider the finite automaton in the following figure.What is the set of reachable states for the input string 0011?
A.	\(\left\{ {{q_0},\;{q_1},\;{q_2}} \right\}\)
B.	\(\left\{ {{q_0},\;{q_1}} \right\}\)
C.	\(\left\{ {{q_0},\;{q_1},\;{q_2},\;{q_3}} \right\}\)
D.	\(\left\{ {{q_3}} \right\}\)
Answer» B. \(\left\{ {{q_0},\;{q_1}} \right\}\)

Discussion

9.	Definition of a language L with alphabet {a} is given as follows:\(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.	2n+1
D.	2k+1
Answer» C. 2n+1

Discussion

10.	Consider the following statements.I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular.II. The class of regular languages is closed under infinite union.Which of the above statements is/are TRUE?
A.	I only
B.	II only
C.	Both I and II
D.	Neither I nor II
Answer» E.

Discussion

11.	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 language is _______.
A.	2
B.	5
C.	3
D.	8
Answer» C. 3

Discussion

12.	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?
A.	{0,1}* - L
B.	L.L
C.	L - {01}
D.	L ∪ {01}
Answer» B. L.L

Discussion

13.	Language L1 is defined by the grammar: S1 → aS1b\|ϵLanguage L2 is defined by the grammar: S2 → abS2\|ϵConsider the following statements:P: L1 is regularQ: L2 is regularWhich one of the following is TRUE?
A.	Both P and Q are true
B.	P is true and Q is false
C.	P is false and Q is true
D.	Both P and Q are false
Answer» D. Both P and Q are false

Discussion

14.	Consider the following regular expressions:(a) r = a(b + a)(b) s = a(a + b)+(c) t = aabChoose the correct answer from the options given below based on the relation between the languages generated by the regular expressions above:
A.	L(r) ⊆ L(s) ⊆ L(t)
B.	L(r) ⊇ L(s) ⊇ L(t)
C.	L(r) ⊇ L(t) ⊇ L(s)
D.	L(s) ⊇ L(t) ⊇ L(r)
Answer» C. L(r) ⊇ L(t) ⊇ L(s)

Discussion

15.	Match the following:P. Lexical analysis1. Graph coloringQ. Parsing2. DFA minimizationR. Register allocation3. Post-order traversalS. Expression evaluation4. Production tree
A.	P – 2, Q – 3, R – 1, S - 4
B.	P – 2, Q – 1, R – 4, S - 3
C.	P – 2, Q – 4, R – 1, S - 3
D.	P – 2, Q – 3, R – 4, S - 1
Answer» D. P – 2, Q – 3, R – 4, S - 1

Discussion

16.	Let δ denote the transition function and \(\hat \delta\) denote the extended transition function of the ϵ-NFA whose transition table is given below: δ ϵ ab→ q0{q2}{q1}{q0}q1{q2}{q2}{q3}q2{q0}ϕ ϕ *q3ϕ ϕ {q2} Then \(\hat \delta \;\left( {{q_2},\;aba} \right)\) is
A.	ϕ
B.	{q0, q1, q3}
C.	{q0, q1, q2}
D.	{q0, q2, q3}
Answer» D. {q0, q2, q3}

Discussion

17.	Consider the following context-free grammars:G1 : S → aS\|B, B → b\|bBG2 : S → aA\|bB, A → aA\|B\|ϵ, B → bB\|ϵ Which one of the following pairs of languages is generated by G1 and G2, respectively?
A.	{ambn\|m > 0 or n > 0} and {ambn\|m > 0 and n > 0}
B.	{ambn\|m > 0 and n > 0} and {ambn\|m > 0 or n ≥ 0}
C.	{ambn\|m ≥ 0 or n > 0} and {ambn\|m > 0 and n > 0}
D.	{ambn\|m ≥ 0 and n > 0} and {ambn\|m > 0 or n > 0}
Answer» E.

Discussion

18.	If A and B are regular languages, then A ∪ B is a _____ language.
A.	regular
B.	non-regular
C.	finite
D.	natural
Answer» B. non-regular

Discussion

19.	If L1 = {an\|n ≥ 0} and L2 = {bn\|n ≥ 0}, consider(I) L1⋅L2 is a regular language(II) L1⋅L2 = {anbn\|n ≥ 0} Which one of the following is CORRECT?
A.	Only (I)
B.	Only (II)
C.	Both (I) and (II)
D.	Neither (I) nor (II)
Answer» B. Only (II)

Discussion

20.	Consider the following statements about the context-free grammar:\(G={\{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 PDAWhich combinations below expresses all the true statements about G?
A.	I only
B.	I and III only
C.	II and III only
D.	I, II and III
Answer» C. II and III only

Discussion

21.	Minimum number of states required in DFA accepting binary strings not ending in “101” is
A.	3
B.	4
C.	5
D.	6
Answer» C. 5

Discussion

22.	A language is said to be ______ if it can be recognised by an NFA (Nondeterministic Finite Automation)
A.	regular
B.	non-regular
C.	non-formal
D.	natural
Answer» B. non-regular

Discussion

23.	How many states are there in a minimum state deterministic finite automaton accepting the language L = {w \| ∈ (0,1)*, number of 0's is divisible by 2, and number of 1's is divisible by 5, respectively}?
A.	7
B.	9
C.	10
D.	11
Answer» D. 11

Discussion

24.	Pushdown automata are _____ machines augmented with additional memory in the form of a stack.
A.	nondeterministic infinite state
B.	deterministic finite state
C.	nondeterministic finite state
D.	deterministic infinite state
Answer» D. deterministic infinite state

Discussion

25.	Choose the correct statement —
A.	A = {an bn \| n = 1, 2, 3, .... } is a regular language
B.	The set B, consisting of all strings made up of only a’s and b’s having equal number of a’s and b’s defines a regular language
C.	L(A * B)∩ B gives the set A
D.	None of the above
Answer» B. The set B, consisting of all strings made up of only a’s and b’s having equal number of a’s and b’s defines a regular language

Discussion

26.	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 (the constant guaranteed by the pumping lemma) for L?
A.	3
B.	5
C.	9
D.	24
Answer» E.

Discussion

27.	For Σ = {a,b} the regular expression r = (aa)(bb)b denotes
A.	Set of strings with 2 a’s and 2 b’s
B.	Set of strings with 2 a’s 2 b’s followed by b
C.	Set of strings with 2 a’s followed by b’s which is a multiple of 3
D.	Set of strings with even number of a’s followed by odd number of b’s
Answer» E.

Discussion

28.	Match List I with List II:LR: Regular language, LCF: Context free languageLREC: Recursive language, LRE: Recursively enumerable language.List IList II(A) Recursively Enumerable language(I) L̅REC ∪ LRE(B) Recursive language(II) L̅CF ∪ LREC(C) Context Free language(III) LR ∩ LCF Choose the correct answer from the options given below:
A.	A - II, B - III, C - I
B.	A - III, B - I, C - II
C.	A - I, B - II, C - III
D.	A - II, B - I, C - III
Answer» D. A - II, B - I, C - III

Discussion

29.	A grammar is defined asA → BCB → x \| BxC → B \| DD → y \| EyE → zThe non-terminal alphabet of the grammar is
A.	{A, B, C, D, E}
B.	{B, C, D, E}
C.	{A, B, C, D, E, x, y, z}
D.	{x, y, z}
Answer» B. {B, C, D, E}

Discussion

30.	Consider the alphabet Σ = {0, 1}, the null/empty string
A.	10(0* + (10)*)1
B.	10(0* + (10))1
C.	1(0 + 10)*1
D.	10(0 + 10)1 + 110(0 + 10)1
Answer» D. 10(0 + 10)1 + 110(0 + 10)1

Discussion

31.	Finite state machine can recognize language generated by ________.
A.	Only context free grammar
B.	Only context sensitive grammar
C.	Only regular grammar
D.	any unambiguous grammar
Answer» D. any unambiguous grammar

Discussion

32.	A finite automata is defined as a ______.
A.	3 - Tuple
B.	4 - Tuple
C.	5 - Tuple
D.	6 - Tuple
Answer» D. 6 - Tuple

Discussion

33.	Consider the languages L1 = Φ and L2 ={a}. Which one of the following represents \({L_1}L_2^* \cup L_1^*\)?
A.	{ϵ}
B.	Φ
C.	a*
D.	{ϵ, a}
Answer» B. Φ

Discussion

34.	Let L1 and L2 be languages over ∑ = {a, b} represented by the regular expressions (a* + b)* and (a + b)* respectively.Which of the following is true with respect to the two languages?
A.	L1 ⊂ L2
B.	L2 ⊂ L1
C.	L1 = L2
D.	L1 ∩ L2 = ϕ
Answer» D. L1 ∩ L2 = ϕ

Discussion

35.	Let L1 = {w ∈ {0, 1}\|w has at least as many occurrences of (110)’s as (011)’s}. Let L2 = {w ∈ {0, 1}\|w has at least as many occurrences of (000)’s as (111)’s}. Which one of the following is TRUE?
A.	L1 is regular but not L2
B.	L2 is regular but not L1
C.	Both L1 and L2 are regular
D.	Neither L1 nor L2 are regular
Answer» B. L2 is regular but not L1

Discussion

36.	Consider the FA shown in fig below which language is accepted by the FA:
A.	(b + a + b)*a
B.	b + (a + b)*b
C.	b + ab
D.	b + a*b
Answer» B. b + (a + b)*b

Discussion

37.	Identify the language generated by the following grammar, where S is the start variable.S → XYX → aX \| aY → aYb \| ϵ
A.	{ambn \| m ≥ n, n > 0}
B.	{ambn \| m ≥ n, n ≥ 0}
C.	{ambn \| m > n, n ≥ 0}
D.	{ambn \| m > n, n > 0}
Answer» D. {ambn \| m > n, n > 0}

Discussion

38.	Pumping lemma for regular language is generally used for proving :
A.	whether two given regular expressions are equivalent
B.	a given grammar is ambiguous
C.	a given grammar is regular
D.	a given grammar is not regular
Answer» E.

Discussion

39.	Let R1 and R2 be regular sets defined over the alphabet, then
A.	R1 ∩ R2 is not regular
B.	R1 ∪ R2 is not regular
C.	∑* - R1 is regular
D.	R1* is not regular
Answer» D. R1* is not regular

Discussion

40.	Let L be the language represented by the regular expression Σ∗0011Σ∗ where Σ={0, 1}. What is the minimum number of states in a DFA that recognizes L̅ (complement of L)?
A.	2
B.	5
C.	6
D.	8
Answer» C. 6

Discussion

37.	Identify the language generated by the following grammar, where S is the start variable.S → XYX → aX \| aY → aYb \| ϵ
A.	{ambn \| m ≥ n, n > 0}
B.	{ambn \| m ≥ n, n ≥ 0}
C.	{ambn \| m > n, n ≥ 0}
D.	{ambn \| m > n, n > 0}
Answer» D. {ambn \| m > n, n > 0}

Explore topic-wise MCQs in Computer Science.

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

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

In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?

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

Number of states in DFA accepting the following language is:L = { an b2m | n, m ≥ 1 }

Consider the following two statements:I. If all states of an NFA are accepting states then the language accepted by the NFA is ∑*.II. There exists a regular language A such that for all languages B, A ∩ B is regular.Which one of the following is CORRECT?

Consider the DFA A given belowWhich of the following are FALSE?1. Complement of L(A) is context-free.2. L(A) = L((110 + 0)(0 + 1)01)3. For the language accepted by A, A is the minimal DFA.4. A accepts all strings over {0, 1} of length at least 2.

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

Definition of a language L with alphabet {a} is given as follows:\(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?

Consider the following statements.I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular.II. The class of regular languages is closed under infinite union.Which of the above statements is/are 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 automation accepting language is _______.

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?

Language L1 is defined by the grammar: S1 → aS1b|ϵLanguage L2 is defined by the grammar: S2 → abS2|ϵConsider the following statements:P: L1 is regularQ: L2 is regularWhich one of the following is TRUE?

Consider the following regular expressions:(a) r = a(b + a)(b) s = a(a + b)+(c) t = aabChoose the correct answer from the options given below based on the relation between the languages generated by the regular expressions above:

Match the following:P. Lexical analysis1. Graph coloringQ. Parsing2. DFA minimizationR. Register allocation3. Post-order traversalS. Expression evaluation4. Production tree

Let δ denote the transition function and \(\hat \delta\) denote the extended transition function of the ϵ-NFA whose transition table is given below: δ ϵ ab→ q0{q2}{q1}{q0}q1{q2}{q2}{q3}q2{q0}ϕ ϕ *q3ϕ ϕ {q2} Then \(\hat \delta \;\left( {{q_2},\;aba} \right)\) is

Consider the following context-free grammars:G1 : S → aS|B, B → b|bBG2 : S → aA|bB, A → aA|B|ϵ, B → bB|ϵ Which one of the following pairs of languages is generated by G1 and G2, respectively?

If A and B are regular languages, then A ∪ B is a _____ language.

If L1 = {an|n ≥ 0} and L2 = {bn|n ≥ 0}, consider(I) L1⋅L2 is a regular language(II) L1⋅L2 = {anbn|n ≥ 0} Which one of the following is CORRECT?

Consider the following statements about the context-free grammar:\(G={\{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 PDAWhich combinations below expresses all the true statements about G?

Minimum number of states required in DFA accepting binary strings not ending in “101” is

A language is said to be ______ if it can be recognised by an NFA (Nondeterministic Finite Automation)

How many states are there in a minimum state deterministic finite automaton accepting the language L = {w | ∈ (0,1)*, number of 0's is divisible by 2, and number of 1's is divisible by 5, respectively}?

Pushdown automata are _____ machines augmented with additional memory in the form of a stack.

Choose the correct statement —

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 (the constant guaranteed by the pumping lemma) for L?

For Σ = {a,b} the regular expression r = (aa)(bb)b denotes

A grammar is defined asA → BCB → x | BxC → B | DD → y | EyE → zThe non-terminal alphabet of the grammar is

Consider the alphabet Σ = {0, 1}, the null/empty string

Finite state machine can recognize language generated by ________.

A finite automata is defined as a ______.

Consider the languages L1 = Φ and L2 ={a}. Which one of the following represents \({L_1}L_2^* \cup L_1^*\)?

Let L1 and L2 be languages over ∑ = {a, b} represented by the regular expressions (a* + b)* and (a + b)* respectively.Which of the following is true with respect to the two languages?

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

Consider the FA shown in fig below which language is accepted by the FA:

Identify the language generated by the following grammar, where S is the start variable.S → XYX → aX | aY → aYb | ϵ

Pumping lemma for regular language is generally used for proving :

Let R1 and R2 be regular sets defined over the alphabet, then

Let L be the language represented by the regular expression Σ∗0011Σ∗ where Σ={0, 1}. What is the minimum number of states in a DFA that recognizes L̅ (complement of L)?

Explore topic-wise MCQs in Computer Science.

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

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

In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?

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

Number of states in DFA accepting the following language is:L = { an b2m | n, m ≥ 1 }

Consider the following two statements:I. If all states of an NFA are accepting states then the language accepted by the NFA is ∑*.II. There exists a regular language A such that for all languages B, A ∩ B is regular.Which one of the following is CORRECT?

Consider the DFA A given belowWhich of the following are FALSE?1. Complement of L(A) is context-free.2. L(A) = L((11*0 + 0)(0 + 1)*0*1*)3. For the language accepted by A, A is the minimal DFA.4. A accepts all strings over {0, 1} of length at least 2.

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

Definition of a language L with alphabet {a} is given as follows:\(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?

Consider the following statements.I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular.II. The class of regular languages is closed under infinite union.Which of the above statements is/are 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 automation accepting language is _______.

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?

Language L1 is defined by the grammar: S1 → aS1b|ϵLanguage L2 is defined by the grammar: S2 → abS2|ϵConsider the following statements:P: L1 is regularQ: L2 is regularWhich one of the following is TRUE?

Consider the following regular expressions:(a) r = a(b + a)*(b) s = a(a + b)+(c) t = aa*bChoose the correct answer from the options given below based on the relation between the languages generated by the regular expressions above:

Match the following:P. Lexical analysis1. Graph coloringQ. Parsing2. DFA minimizationR. Register allocation3. Post-order traversalS. Expression evaluation4. Production tree

Let δ denote the transition function and \(\hat \delta\) denote the extended transition function of the ϵ-NFA whose transition table is given below: δ ϵ ab→ q0{q2}{q1}{q0}q1{q2}{q2}{q3}q2{q0}ϕ ϕ *q3ϕ ϕ {q2} Then \(\hat \delta \;\left( {{q_2},\;aba} \right)\) is

Consider the following context-free grammars:G1 : S → aS|B, B → b|bBG2 : S → aA|bB, A → aA|B|ϵ, B → bB|ϵ Which one of the following pairs of languages is generated by G1 and G2, respectively?

If A and B are regular languages, then A ∪ B is a _____ language.

If L1 = {an|n ≥ 0} and L2 = {bn|n ≥ 0}, consider(I) L1⋅L2 is a regular language(II) L1⋅L2 = {anbn|n ≥ 0} Which one of the following is CORRECT?

Consider the following statements about the context-free grammar:\(G={\{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 PDAWhich combinations below expresses all the true statements about G?

Minimum number of states required in DFA accepting binary strings not ending in “101” is

A language is said to be ______ if it can be recognised by an NFA (Nondeterministic Finite Automation)

How many states are there in a minimum state deterministic finite automaton accepting the language L = {w | ∈ (0,1)*, number of 0's is divisible by 2, and number of 1's is divisible by 5, respectively}?

Pushdown automata are _____ machines augmented with additional memory in the form of a stack.

Choose the correct statement —

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 (the constant guaranteed by the pumping lemma) for L?

For Σ = {a,b} the regular expression r = (aa)*(bb)*b denotes

A grammar is defined asA → BCB → x | BxC → B | DD → y | EyE → zThe non-terminal alphabet of the grammar is

Consider the alphabet Σ = {0, 1}, the null/empty string

Finite state machine can recognize language generated by ________.

A finite automata is defined as a ______.

Consider the languages L1 = Φ and L2 ={a}. Which one of the following represents \({L_1}L_2^* \cup L_1^*\)?

Let L1 and L2 be languages over ∑ = {a, b} represented by the regular expressions (a* + b)* and (a + b)* respectively.Which of the following is true with respect to the two languages?

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

Consider the FA shown in fig below which language is accepted by the FA:

Identify the language generated by the following grammar, where S is the start variable.S → XYX → aX | aY → aYb | ϵ

Pumping lemma for regular language is generally used for proving :

Let R1 and R2 be regular sets defined over the alphabet, then

Let L be the language represented by the regular expression Σ∗0011Σ∗ where Σ={0, 1}. What is the minimum number of states in a DFA that recognizes L̅ (complement of L)?

Consider the DFA A given belowWhich of the following are FALSE?1. Complement of L(A) is context-free.2. L(A) = L((110 + 0)(0 + 1)01)3. For the language accepted by A, A is the minimal DFA.4. A accepts all strings over {0, 1} of length at least 2.

Consider the following regular expressions:(a) r = a(b + a)(b) s = a(a + b)+(c) t = aabChoose the correct answer from the options given below based on the relation between the languages generated by the regular expressions above:

For Σ = {a,b} the regular expression r = (aa)(bb)b denotes

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