COMP2048: Theory of Computing - Week 3 Flashcards

Flashcards covering Non-deterministic Finite Automata (NFA), Subset Construction, Regular Operations, and the Pumping Lemma for Regular Languages based on Week 3 lecture notes.

What are three characteristics that distinguish a Non-deterministic Finite Automaton (NFA) from a DFA?

1) From each state and for each symbol there are zero, one, or more possible next states; 2) transitions can occur without consuming input ($\epsilon$ transitions); 3) it can be in multiple states after reading the kth symbol.

According to the provided notes, what are the three equivalent ways to describe the set of Regular Languages?

The set of languages recognized by DFAs, the set of languages recognized by NFAs, and the set of languages described by regular expressions.

In the worst-case scenario, how many states can a DFA have when converted from an $n$-state NFA via subset construction?

Up to $2^n$ states.

In the Subset Construction method to convert NFA $N = (Q, \Sigma, \delta, q_0, F)$ to DFA M = (Q', \Sigma, \delta', q_0', F')$, how is the new state set Q'$$ defined?

$Q' = P(Q) = \{R \mid R \subseteq Q\}$ (the power set of the NFA states).

How is the transition function $\delta'(R, a)$ defined for a DFA constructed from an NFA via Subset Construction?

$\delta'(R, a) = \bigcup_{r \in R} \delta(r, a)$, where $R \in Q'$ and $a \in \Sigma$.

What is the condition for a state $R \in Q'$ to be an accepting state ($F'$) in a DFA converted from an NFA?

$R$ contains at least one accept state of the original NFA $N$.

What is the formal definition of the concatenation of two regular languages $L_1$ and $L_2$?

$L_1L_2 = \{w \in \Sigma^* \mid w = xy \text{ such that } x \in L_1, y \in L_2\}$.

How is the Star operation ($L^*$) defined in terms of concatenations?

$L^* = \{\epsilon\} \cup L \cup L^2 \cup L^3 \cup \dots$ where $L^k$ is the $k$ times concatenation of $L$.

What are the three base cases for constructing an NFA from a regular expression?

1) $\emptyset$ (the empty set); 2) $\epsilon$ (the empty string); 3) $a \in \Sigma$ (a single symbol from the alphabet).

What is the formal statement of the Pumping Lemma for Regular Languages?

If $L$ is a regular language, there exists a constant $p \geq 1$ (pumping length) such that for every string $w \in L$ with $|w| \geq p$, there exist strings $x, y, z$ such that $w = xyz$, $|y| \geq 1$, $|xy| \leq p$, and for all $i \geq 0$, the string $xy^iz \in L$.

What is the logical approach to proving a language is not regular using the Pumping Lemma?

Use proof by contradiction: 1) Assume $L$ is regular; 2) Apply the Pumping Lemma to find a pumping length $p$; 3) Pick a string $w \in L$ such that $|w| \geq p$; 4) Show that for all possible decompositions $w = xyz$ meeting the lemma's conditions, there exists an $i$ such that $xy^iz \notin L$.

In the example proof, why is the language $L = \{1^n0^n \mid n > 0\}$ shown to be non-regular?

When picking $w = 1^p0^p$, any decomposition $w = xyz$ where $|xy| \leq p$ results in $y$ containing only 1s. Thus, pumping $y$ (e.g., $xy^2z$) will result in a string with more 1s than 0s, which is not in $L$.