Virtual Labs

In automata theory, which class of languages can be represented exactly by Regular Expressions (RE)?

a: Context-Free Languages Explanation

Explanation

b: Regular Languages Explanation

Explanation

c: Deterministic Context-Free Languages Explanation

Explanation

d: Recursively Enumerable Languages Explanation

Explanation

During Thompson’s Construction, how is concatenation of two NFAs (N1 for R1 and N2 for R2) implemented?

a: By merging the final state of N1 with the start state of N2 using an ε-transition. Explanation

Explanation

b: By duplicating the states of N1 and N2 into a larger automaton. Explanation

Explanation

c: By replacing input symbols of N1 with those of N2. Explanation

Explanation

d: By creating a new single state that represents both automata. Explanation

Explanation

Which of the following is TRUE regarding the equivalence of NFAs and DFAs?

a: Every NFA can be converted to a DFA using the subset construction method. Explanation

Explanation

b: Every DFA can be converted to an NFA, but the reverse is not true. Explanation

Explanation

c: NFAs recognize strictly more languages than DFAs. Explanation

Explanation

d: DFAs require ε-transitions to simulate NFAs. Explanation

Explanation

When applying Kleene Star in Thompson’s Construction for an expression R*, what structural modification is made?

a: A new start state is created with ε-transitions to R and to a new final state, and R’s final connects back to its start with ε. Explanation

Explanation

b: The automaton is simply duplicated infinitely many times. Explanation

Explanation

c: Each transition symbol is replaced with multiple ε-transitions. Explanation

Explanation

d: A new final state is created that directly absorbs all input without processing R. Explanation

Explanation

Why is ε-closure important in the subset construction algorithm for converting NFA to DFA?

a: It ensures that all possible ε-moves from a set of states are considered as part of the DFA state. Explanation

Explanation

b: It reduces the number of states in the resulting DFA. Explanation

Explanation

c: It eliminates nondeterminism by removing redundant transitions. Explanation

Explanation

d: It guarantees that the DFA will always be minimal. Explanation

Explanation

Conversion of RE to NFA