Regular Expressions and FSA's

en · official · sha256:13045159c908f52ecb9342f0665ccf9e3c4da940f3965c3cdf4c3464ecfe3554

\begin{theorem}\label{closure} The intersection of two regular languages is a regular language. The union of two regular languages is a regular language. The concatenation of two regular languages is a regular language. The complement of a regular language is a regular language. The Kleene closure of a regular language is a regular language. \end{theorem}

Referencing norms: ClosureComplement, ClosureConcatenation, ClosureIntersection, ClosureStar, ClosureUnion

en · official · sha256:6a10f0f0139acf73ebb48962003d69550ca7cac680b7e1fe8860a220ac5f5df9

\begin{definition} Formally, a \nw{deterministic finite-state automaton} $M$ is specified by 5 components: $M=(Q, \Sigma, q_0, \delta, F)$ where \begin{itemize} \item $Q$ is a finite set of states; \item $\Sigma$ is an alphabet called the {\em input alphabet}; \item $q_0 \in Q$ is a state which is designated as the {\em start state}; \item $F$ is a subset of $Q$; the states in $F$ are states designated as {\em final} or {\em accepting} states; \item $\delta$ is a transition function that takes $<$state, input symbol$>$ pairs and maps each one to a state: $\delta : Q \times \Sigma \rightarrow Q$. To say $\delta(q,a) = q'$ means that if the machine is in state $q$ and the input symbol $a$ is consumed, then the machine will move into state $q'$. The function $\delta$ must be a total function, meaning that $\delta(q,a)$ must be defined for every state $q$ and every input symbol $a$. (Recall also that, according to the definition of a function, there can be only one output for any particular input. This means that for any given $q$ and $a$, $\delta(q,a)$ can have only one value. This is what makes the finite-state automaton deterministic: given the current state and input symbol, there is only one possible move the machine can make.) \end{itemize} \end{definition}

Referencing norms: DeterministicAutomaton

en · official · sha256:10e63d42425d06d53bf28bcdf18a48ba3f44c51d2b00ee08afd14c64071e7baf

\begin{definition} Let $M=(Q, \Sigma, q_0, \delta, F)$. A string $w \in \Sigma^*$ is \nw{accepted} by $M$ iff $\dstar(q_0, w) \in F$. \ \ (Don't get confused by the notation. Remember, it's just a shorter and neater way of saying ``$w \in \Sigma^*$ is accepted by $M$ if and only if the state that $M$ will end up in if it starts in $q_0$ and consumes $w$ is one of the states in $F$.") The \nw{language accepted by $M$}, denoted $L(M)$, is the set of all strings $w \in \Sigma^*$ that are accepted by $M$: $L(M) = \{ w \in\Sigma^* \ | \ \delta^*(q_0, w) \in F\}$. \end{definition}

Referencing norms: LanguageAcceptedByDfa

en · official · sha256:66f10447186a2c0a0486937f6a7f59920d9ebf0d8ef702e785150586024d73b5

\begin{theorem}\label{T-DFAeqReg} Every language that is accepted by a DFA or an NFA is generated by a regular expression. \end{theorem}

Referencing norms: KleeneSecondHalf, KleeneSecondHalfProofStaysInSource

en · official · sha256:c100e631d2a1d61625400a812313a3edf117fe4711555af2116495d4698e9076

\begin{definition} A language over an alphabet $\Sigma$ is a subset of $\Sigma^*$. Thus, a language over $\Sigma$ is an element of ${\cal P}(\Sigma^*)$, the power set of $\Sigma^*$. \end{definition}

Referencing norms: LanguageOverAlphabet

en · official · sha256:0a3d3c06d0375ecc5eb9f21e6c75013865c124087b177dd2c26ec2dac6aa98da

\begin{definition} Formally, a nondeterministic finite-state automaton $M$ is specified by 5 components: $M=(Q, \Sigma, q_0, \partial, F)$ where \begin{itemize} \item $Q$, $\Sigma$, $q_0 $ and $F$ are as in the definition of DFAs; \item $\partial$ is a transition function that takes $<$state, input symbol$>$ pairs and maps each one to a set of states. To say $\partial(q,a) = \{q_1, q_2, \ldots , q_n\}$ means that if the machine is in state $q$ and the input symbol $a$ is consumed, then the machine may move directly into any one of states $q_1, q_2, \ldots , q_n$. The function $\partial$ must also be defined for every $<$state,$\varep$$>$ pair. To say $\partial(q,\varep) = \{q_1, q_2, \ldots , q_n\}$ means that there are direct $\varep$-transitions from state $q$ to each of $q_1, q_2, \ldots , q_n$. The formal description of the function $\partial$ is $\partial : Q \times (\Sigma \cup \{\varep\}) \rightarrow \POW(Q)$. \end{itemize} \end{definition}

Referencing norms: NondeterministicAutomaton

en · official · sha256:be56b2f6f7c74060d96b3dae52661a240ac91d7edeee7f62a35376e6a65bc4a2

\begin{definition} Let $M= (Q, \Sigma, q_0, \partial, F)$ be a nondeterministic finite-state automaton. The string $\winss$ is \nw{accepted} by $M$ iff $\pstar(q_0,w)$ contains at least one state $q_F \in F$. The \nw{language accepted by $M$}, denoted $L(M)$, is the set of all strings $\winss$ that are accepted by $M$: $L(M) = \{ w \in \Sigma^* \ | \ \pstar(q_0, w) \cap F \not= \emptyset\}$. \end{definition}

Referencing norms: LanguageAcceptedByNfa

en · official · sha256:44f394d3c61c2751847f8d32e4ab1d2da2cd962e8537901db51e1a75e7bc2f30

\begin{theorem} For any alphabet $\Sigma$, the number of languages over $\Sigma$ is uncountable. \end{theorem}

Referencing norms: UncountabilityProofStaysInSource, UncountablyManyLanguages

en · official · sha256:2c2875d1283cb8bb53812b782bc4d15f83fea1e359ef2e7bf53a1759a8967181

\begin{definition}\label{lgbre} The \nw{language generated by a regular expression $r$}, denoted $L(r)$, is defined as follows: \begin{enumerate} \item $L(\Phi) = \emptyset$, i.e.\ no strings match $\Phi$; \item $L(\varep) = \{\varep\}$, i.e.\ $\varep$ matches only the empty string; \item $L(a) = \{a\}$, i.e.\ $a$ matches only the string $a$; \item $L(r_1\REOR r_2) = L(r_1) \cup L(r_2)$, i.e.\ $r_1\REOR r_2$ matches strings that match $r_1$ or $r_2$ or both; \item $L(r_1r_2) = L(r_1)L(r_2)$, i.e.\ $r_1r_2$ matches strings of the form ``something that matches $r_1$ followed by something that matches $r_2$"; \item $L(r_1^*) = (L(r_1))^*$, i.e.\ $r_1^*$ matches sequences of 0 or more strings each of which matches $r_1$. \item $L((r_1)) = L(r_1)$, i.e.\ $(r_1)$ matches exactly those strings matched by $r_1$. \end{enumerate} \end{definition}

en · official · sha256:4f5b55c44a77f8e11c90071d562ff2a986963473b251a184b98180e0d9650c20

\begin{definition} Let $\Sigma$ be an alphabet. Then the following patterns are \nw{regular expressions} over $\Sigma$: \begin{enumerate} \item $\Phi$ and $\varep$ are regular expressions; \item $a$ is a regular expression, for each $a \in \Sigma$; \item if $r_1$ and $r_2$ are regular expressions, then so are $r_1\REOR r_2$, $r_1\cdot r_2$, $r_1^*$ and $(r_1)$ (and of course, $r_2^*$ and $(r_2)$). As in concatenation of strings, the $\cdot$ is often left out of the second expression. (Note: the order of precedence of operators, from lowest to highest, is $\REOR $, $\cdot$, $*$.) \end{enumerate} No other patterns are regular expressions. \end{definition}

Referencing norms: RegexpOverAlphabet

en · official · sha256:6c4135a4330cf4b5886c874258bd18591f8c9d036606a3f4697272f74383d76b

\begin{definition} A language is {\em regular} if it is generated by a regular expression. \end{definition}

Referencing norms: RegularLanguage

en · official · sha256:06a5b8575f7eb602c79e0e9014d384dec08094ba12d40e8ffd0d83b0c313f6b1

\begin{theorem}\label{retonfa} Every language generated by a regular expression can be recognized by an NFA. \end{theorem}

Referencing norms: KleeneFirstHalf, KleeneFirstHalfProofStaysInSource

en · official · sha256:a82f0834eff1f9f72c503aa76fb4ad08e0e39e693069b718bbc838852507f26e

\begin{theorem} Every language that is accepted by an NFA is accepted by a DFA. \end{theorem}

Referencing norms: SubsetConstructionProofStaysInSource, SubsetConstructionTheorem