NFA to DFA conversion in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to represent the initial state of the DFA as the epsilon-closure of the NFA's start state.

Compiler Design

dfa_start_state = epsilon_closure([1])

Drag options to blanks, or click blank then click option'

Anfa_final_state

Bdfa_final_state

Cnfa_start_state

Ddfa_start_state

Attempts:

3 left

💡 Hint

Common Mistakes

Using the NFA final state instead of the start state.

Confusing DFA start state with NFA start state.

The DFA's start state is the epsilon-closure of the NFA's start state, which includes all states reachable without consuming input.

2fill in blank

medium

Complete the code to find the set of NFA states reachable from a given DFA state on input symbol 'a'.

Compiler Design

reachable_states = move([1], 'a')

Drag options to blanks, or click blank then click option'

Adfa_state

Bnfa_start_state

Cdfa_final_state

Dnfa_state

Attempts:

3 left

💡 Hint

Common Mistakes

Passing a single NFA state instead of the DFA state set.

Using the NFA start or final state incorrectly.

The move function takes a set of NFA states (which represent a DFA state) and an input symbol, returning the set of states reachable on that symbol.

3fill in blank

hard

Fix the error in the code that computes the epsilon-closure of a set of states.

Compiler Design

def epsilon_closure(states):
    stack = list(states)
    closure = set(states)
    while stack:
        state = stack.pop()
        for next_state in [1](state):
            if next_state not in closure:
                closure.add(next_state)
                stack.append(next_state)
    return closure

Drag options to blanks, or click blank then click option'

Ainput_symbols

Bmove

Cfinal_states

Depsilon_transitions

Attempts:

3 left

💡 Hint

Common Mistakes

Using move instead of epsilon_transitions.

Using input symbols or final states incorrectly.

The epsilon_closure function must use the epsilon_transitions function to find states reachable without consuming input.

4fill in blank

hard

Fill both blanks to complete the dictionary comprehension that builds the DFA transition table from the NFA.

Compiler Design

dfa_transitions = {state: {symbol: [1](epsilon_closure(move(state, symbol))) for symbol in [2] for state in dfa_states}

Drag options to blanks, or click blank then click option'

Afrozenset

Binput_symbols

Cset

Dfinal_states

Attempts:

3 left

💡 Hint

Common Mistakes

Using set instead of frozenset, which is not hashable.

Using final_states instead of input_symbols.

The DFA transitions map each state and input symbol to a frozenset of NFA states representing the new DFA state. The input_symbols set lists all possible input characters.

5fill in blank

hard

Fill in the blanks to complete the code that identifies DFA final states from NFA final states.

Compiler Design

dfa_final_states = {state for state in dfa_states if state & [1] != [2]

Drag options to blanks, or click blank then click option'

Anfa_final_states

Bnfa_start_states

Cset()

Ddfa_start_state

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing start states with final states.

Using empty set incorrectly.

DFA final states are those that include at least one NFA final state. The code checks that the intersection with NFA final states is not the empty set.