Regular Languages: Master the Fundamentals of Formal Languages

Question 1

Which of the following regular expressions matches hexadecimal numbers (base 16) that consist of one or more hexadecimal digits (0-9 or a-f)?

Accepted Answer

[0-9a-f]{1,}

Answer

[0-9]{1,}

Answer

[a-f]{1,}

Answer

a-f[0-9]{1,}

Question 2

Which technique is commonly used to convert a regular expression to an equivalent non-deterministic finite automaton (NFA)?

Accepted Answer

Thompson's construction

Answer

Myhill-Nerode theorem

Answer

Kleene's theorem

Answer

Pumping lemma

Question 3

Which of the following is an invalid regular expression?

Accepted Answer

a.b

Answer

(a + b)*

Answer

a|b

Answer

a?

Question 4

Which of the following finite automata recognizes the language {a^n b^m | n, m >= 0}?

Accepted Answer

[Diagram of a finite automaton with states q0, q1, q2, and transitions (q0, a, q1), (q1, a, q1), (q1, b, q2), (q2, b, q2)]

Answer

[Diagram of a finite automaton with states q0, q1, q2, and transitions (q0, a, q1), (q1, b, q2), (q2, a, q2)]

Answer

[Diagram of a finite automaton with states q0, q1, and transitions (q0, a, q1), (q1, b, q0)]

Answer

[Diagram of a finite automaton with states q0, q1, q2, and transitions (q0, a, q1), (q1, a, q1), (q1, b, q2), (q2, a, q0)]

Question 5

Which regular expression is equivalent to the NFA [Diagram of an NFA with states q0, q1, q2, and transitions (q0, a, q1), (q1, a, q2), (q1, b, q1), (q2, b, q2)]?

Accepted Answer

a(a|b)*

Answer

(ab)*

Answer

(a|b)(a|b)*

Answer

(a|b)*a

Question 6

Which of the following is NOT a limitation of regular languages?

Accepted Answer

Can recognize ambiguous languages

Answer

Cannot recognize context-sensitive languages

Answer

Cannot recognize recursive languages

Answer

Cannot recognize languages with unbounded nesting

Question 7

What is the pumping lemma for regular languages?

Accepted Answer

If L is a regular language, then there exists a constant n such that for any string w in L with |w| ≥ n, there is some way to split w into three parts u, v, and x such that |v| ≥ 1, |uxv| ≤ n, and uv^ix ∈ L for all i ≥ 0.

Answer

If L is a regular language, then there exists a constant n such that for any string w in L with |w| ≥ n, there is some way to split w into three parts u, v, and x such that |v| ≥ 1, |uxv| ≤ n, and uv^i ∈ L for all i ≤ 0.

Question 8

Which of the following is a context-free language but not a regular language?

Accepted Answer

{a^n b^m | n ≥ 0, m ≥ 0, n ≠ m}

Answer

{a*b*}

Answer

{a^n | n ≥ 0}

Question 9

What is the Kleene star operation?

Accepted Answer

The Kleene star operation, denoted by *, is a unary operation on regular expressions that produces a new regular expression that matches any number of repetitions of the original regular expression.

Answer

The Kleene star operation, denoted by *, is a binary operation on regular expressions that produces a new regular expression that matches any number of repetitions of the two original regular expressions.

Question 10

What is the fundamental distinction between a Deterministic Finite Automaton (DFA) and a Non-Deterministic Finite Automaton (NFA)?

Accepted Answer

A DFA possesses only one transition for each input symbol from every state, whereas an NFA can have multiple transitions for the same input symbol from the same state.

Answer

A DFA has just one starting state while an NFA can have multiple starting states.

Question 11

Which of the following is not a recognized type of finite automaton?

Accepted Answer

Turing machine

Answer

Pushdown Automaton

Answer

Nondeterministic Finite Automaton (NFA)

Answer

Deterministic Finite Automaton (DFA)

Question 12

Which closure property is exhibited by regular languages?

Accepted Answer

Closure under intersection

Answer

Closure under concatenation but not star

Answer

Closure under union but not intersection

Question 13

Identify a necessary condition for a language to be considered regular.

Accepted Answer

Recognition by a finite automaton

Answer

Classification as a recursively enumerable language

Answer

Classification as a context-free language

Answer

Classification as a decidable language

Question 14

State the Pumping Lemma for regular languages.

Accepted Answer

For a regular language L, there exists a number p such that for any string w in L with |w| ≥ p, w can be divided into three parts: u, v, and x, such that |v| ≥ 1, |uvx| ≤ p, and uv^ix is in L for all i ≥ 0

Answer

For a regular language L, there exists a number p such that for any string w in L with |w| ≥ p, w can be divided into two parts: u and v, such that |u| ≥ 1, |v| ≥ 1, and uv is in L

Question 15

Which of the following is an essential property of regular languages?

Accepted Answer

Regular languages are recognized by finite automata.

Answer

Regular languages are not closed under concatenation.

Answer

Regular languages are context-sensitive.

Answer

Regular languages are closed under intersection.

Question 16

What is the difference between a regular expression and a regular grammar?

Accepted Answer

A regular expression is a compact representation of a regular language, while a regular grammar is a set of production rules that generate the language.

Answer

A regular grammar is more concise than a regular expression.

Answer

A regular expression can represent any language, while a regular grammar cannot.

Question 17

Consider the regular expression (a|b)*abb. Which of the following strings is in the language defined by this regular expression?

Accepted Answer

abb

Answer

aba

Answer

aa

Question 18

Which of the following is NOT a closure property of regular languages?

Accepted Answer

Intersection with a context-free language

Answer

Union

Answer

Concatenation

Answer

Kleene star

Question 19

Which of the following regular expressions represents the language of all strings over {a, b} that contain at least one a and end with b?

Accepted Answer

a(a|b)*b

Answer

a(a|b)*

Answer

a*|b*

Answer

(a|b)*

Question 20

Which of the following is a disadvantage of using finite automata to represent regular languages?

Accepted Answer

They can be inefficient for some languages.

Answer

They are not deterministic.

Answer

They are difficult to construct.

Answer

They are not as expressive as regular expressions.

Question 21

Which of the following operations on regular languages is NOT closed?

Accepted Answer

Intersection with context-free languages

Answer

Concatenation

Answer

Complement

Answer

Union

Question 22

Which of the following techniques can be used to convert a non-deterministic finite automaton (NFA) to a deterministic finite automaton (DFA)?

Accepted Answer

Subset construction

Answer

Pumping lemma

Answer

Closure under union

Answer

Myhill-Nerode theorem

Question 23

State the Pumping Lemma for Regular Languages.

Accepted Answer

For any regular language L, there exists a constant n such that every string in L of length at least n can be divided into three parts (u, v, w) such that uv^i w ∈ L for all i ≥ 0.

Answer

For any regular language L, there exists a constant n such that every string in L of length greater than n contains a repeated substring.

Question 24

The Myhill-Nerode theorem states that a language is regular if and only if:

Accepted Answer

Its Myhill-Nerode equivalence relation has a finite number of equivalence classes.

Answer

It can be recognized by a Turing machine.

Answer

It can be generated by a context-free grammar.

Answer

It can be expressed using a finite number of symbols.

Question 25

Which finite automaton recognizes the language of strings containing an even number of '0's?

Accepted Answer

A DFA with two states, one initial and one accepting. Transitions on '0' lead to the other state, while transitions on '1' remain in the current state.

Answer

A DFA with three states, one initial and two accepting, with transitions on '0' and '1' between them.

Answer

A DFA with two states, both accepting, with transitions on '0' and '1' between them.

Question 26

Regular languages are closed under which of the following operations?

Accepted Answer

Union, intersection, and complement.

Answer

Union and complement, but not intersection.

Answer

Union and intersection, but not complement.

Answer

Intersection and complement, but not union.

Question 27

Which operation on regular languages is not always computable?

Accepted Answer

Complement of a non-regular language.

Answer

Union of two regular languages.

Answer

Intersection of two regular languages.

Answer

Concatenation of two regular languages.

Question 28

A practical application of regular languages is:

Accepted Answer

Lexical analysis in compilers.

Answer

Developing artificial intelligence systems.

Answer

Solving complex mathematical problems.

Answer

Analyzing complex social networks.

Question 29

Which regular expression is equivalent to (a*b)?

Accepted Answer

a*(ε|b)

Answer

a*|b

Answer

(a*b)*

Answer

a*b*

Question 30

Which finite automaton is equivalent to the regular expression (a|b)*ab?

Accepted Answer

A DFA with three states, one initial and one accepting. Transitions on 'a' and 'b' lead to a second state. From the second state, 'a' transitions to the accepting state, and 'b' leads back to the second state.

Answer

A DFA with two states, both accepting, with transitions on 'a' and 'b' between them.

Answer

A DFA with three states, one initial and one accepting, with transitions on 'a' and 'b' between them.

Question 31

The Pumping Lemma for regular languages is primarily used to:

Accepted Answer

Prove that a language is not regular.

Answer

Convert a regular expression to a DFA.

Answer

Simplify a regular expression.

Answer

Construct a DFA for a given regular language.

Question 32

Which of the following is NOT a closure property of regular languages?

Accepted Answer

They are not closed under intersection with non-regular languages.

Answer

They are closed under union.

Answer

They are closed under concatenation.

Question 33

Given the regular expression (a|b)*, which of the following strings is NOT accepted by the corresponding finite automaton?

Accepted Answer

ababaab

Answer

abab

Answer

aaaa

Answer

bb

Question 34

Which of the following statements best describes the relationship between regular expressions and finite automata?

Accepted Answer

Every regular expression can be represented by a finite automaton, and vice versa.

Answer

Every finite automaton can be represented by a regular expression, but not vice versa.

Answer

Every regular expression can be represented by a finite automaton, but not vice versa.

Question 35

Consider the language L = {a^n b^n | n ≥ 0}. Which of the following statements is correct?

Accepted Answer

L is not regular.

Answer

L is regular and can be represented by a finite automaton.

Answer

L is context-free but not regular.

Answer

L is regular and can be represented by a regular expression.

Question 36

In a finite automaton, the transition δ(q1, a) = q2 indicates that:

Accepted Answer

When the automaton is in state q1 and reads the input symbol 'a', it transitions to state q2.

Answer

When the automaton is in state q2, it can read any input symbol and transition to state q1.

Answer

When the automaton is in state q1, it can read an arbitrary input symbol and transition to state q2.

Answer

When the automaton is in state q2 and reads the input symbol 'a', it transitions to state q1.

Question 37

Which of the following regular expressions represents the language of all strings over the alphabet {a, b} that contain at least one 'a'?

Accepted Answer

(b*a(a|b)*)

Answer

(a|b)*

Answer

b*a*

Answer

a(a|b)*

Question 38

Compared to a deterministic finite automaton (DFA), a nondeterministic finite automaton (NFA) may have:

Accepted Answer

The same number of states.

Answer

One less state.

Answer

One more state.

Question 39

What is the purpose of the 'ε' transition in a nondeterministic finite automaton (NFA)?

Accepted Answer

To allow the NFA to move between states without consuming an input symbol.

Answer

To mark the accepting state of the NFA.

Answer

To mark the start state of the NFA.

Question 40

Which of the following is a common application of regular languages in computer science?

Accepted Answer

Lexical analysis in compilers.

Answer

Developing artificial intelligence algorithms.

Answer

Simulating physical systems.

Answer

Solving complex mathematical problems.

Question 41

The language consisting of all strings over the alphabet {a, b} that contain exactly two 'a's can be classified as:

Accepted Answer

Regular.

Answer

Context-sensitive but not context-free.

Answer

Context-free but not regular.

Answer

Recursively enumerable but not context-sensitive.

Question 42

Which of the following languages is NOT a regular language?

Accepted Answer

{a^n b^n | n >= 0}

Answer

{a, b, ab, ba}

Answer

{a^n b^m | n, m >= 0}

Answer

{a^n b | n >= 0}

Question 43

Which regular expression represents the language of strings with an even number of 'a's?

Accepted Answer

(b*ab*ab*)*

Answer

(a*b*)*

Answer

(ab)*

Answer

(aa)*

Question 44

Given a Deterministic Finite Automaton (DFA) with 5 states, what is the maximum number of distinct states reachable from the start state?

Accepted Answer

5

Answer

Infinite

Answer

4

Answer

6

Question 45

Which of the following represents a valid transition function for a Deterministic Finite Automaton (DFA) recognizing the language of strings ending with 'ab'?

Accepted Answer

{ (q0, a) -> q1, (q1, b) -> q2, (q2, a) -> q1, (q2, b) -> q2 }

Answer

{ (q0, a) -> q1, (q1, a) -> q2, (q2, b) -> q0 }

Answer

{ (q0, a) -> q1, (q1, b) -> q0, (q0, b) -> q0 }

Question 46

Which of the following statements about regular languages is TRUE?

Accepted Answer

The intersection of two regular languages is always regular.

Answer

The complement of a regular language is always non-regular.

Answer

The union of a regular language and a non-regular language is always non-regular.

Question 47

The pumping lemma is used to prove that a language is:

Accepted Answer

Not regular

Answer

Regular

Answer

Context-free

Question 48

Which of the following is NOT a typical application of regular languages?

Accepted Answer

Compiling high-level programming languages

Answer

Lexical analysis in compilers

Answer

Network protocol analysis

Answer

Pattern matching in text editors

Question 49

How does a Nondeterministic Finite Automaton (NFA) differ from a Deterministic Finite Automaton (DFA)?

Accepted Answer

An NFA can have multiple transitions from a single state on the same input symbol.

Answer

An NFA can accept an infinite number of strings.

Answer

An NFA has a unique start state.

Question 50

What is the core process involved in converting an NFA to a DFA?

Accepted Answer

Constructing a DFA with states representing subsets of NFA states.

Answer

Simply removing non-deterministic transitions from the NFA.

Answer

Adding new states to the NFA until it becomes deterministic.