Finite automata (DFA and NFA) in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the start state of a DFA.

Compiler Design

dfa_start_state = "[1]"

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

Aq0

Bstart

Cinitial

Dstate1

Attempts:

3 left

💡 Hint

Common Mistakes

Using generic names like 'start' or 'initial' instead of the standard 'q0'.

Confusing the start state with accepting states.

The start state of a DFA is commonly labeled as q0. This is the initial state where the automaton begins processing input.

2fill in blank

medium

Complete the code to represent the transition function for a DFA from state q0 on input 'a'.

Compiler Design

transition_function = {('q0', 'a'): '[1]'}

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

Aq0

Berror

Cq1

Dq2

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning the same state as the next state without reason.

Using 'error' as a state instead of a valid state name.

In a DFA, the transition function maps a state and input symbol to exactly one next state. Here, from q0 on input 'a', the next state is q1.

3fill in blank

hard

Fix the error in the NFA transition representation for state q1 on input 'ε' (epsilon).

Compiler Design

nfa_transitions = {('q1', '[1]'): ['q2', 'q3']}

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

Ae

Bε

Cepsilon

Dlambda

Attempts:

3 left

💡 Hint

Common Mistakes

Using the word 'epsilon' instead of the symbol 'ε'.

Using 'e' which can be confused with other meanings.

The standard symbol for epsilon transitions in NFAs is the Greek letter ε. Using this symbol correctly represents transitions without consuming input.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps each state to its set of accepting states in a DFA.

Compiler Design

accepting_states = {state: [1] for state in states if state [2] accepting}

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

ATrue

Bin

C==

DFalse

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' instead of 'in' for membership check.

Assigning 'False' to accepting states.

The dictionary comprehension assigns True to states that are in the accepting set. The keyword in checks membership.

5fill in blank

hard

Fill all three blanks to define a function that checks if a given string is accepted by a DFA.

Compiler Design

def is_accepted(dfa, input_str):
    state = dfa['[1]']
    for symbol in input_str:
        state = dfa['[2]'].get((state, symbol), None)
        if state is [3]:
            return False
    return state in dfa['accepting_states']

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

Astart_state

Btransitions

CNone

DFalse

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'False' instead of 'None' to check missing transitions.

Confusing 'start_state' with 'accepting_states'.

The function starts from the start_state, uses the transitions dictionary to move between states, and returns False if no valid transition exists (represented by None).