You're given the
statement of a proposed theorem, and you're supposed to write
the specification of the algorithm that would prove the
theorem. We're looking for the specification only, not the
actual algorithm. I.e. just
Input:
NDFAs M1 = (Q1,Σ1,Δ1,s1,W1) and
M2 = (Q2,Σ2,Δ2,s2,W2), where
Q1 ∩ Q2 = ∅
Output: NDFA M such that
L(M) = L(M1)L(M2)
... without actually telling you how to build the machine.
-
Proposed Theorem
If languages L1 and L2 are both accepted
by nondeterministic finite automata, then L1 ∪
L2 is accpeted by a nondeterministic finite
automaton.
Proof requires an algorithm with specification: ?
-
Proposed Theorem
If language L is accepted by a deterministic
finite automaton, then L* is accepted
by a deterministic finite automaton.
Proof requires an algorithm with specification: ?
-
Proposed Theorem
If language L ⊆ Σ* is accepted by a
nondeterministic
finite automaton, and $w \in \Sigma^*$,
then the language of all string in $L$ that do not contain
$w$ as a substring is accepted by a
non-deterministic finite automaton.
Proof requires an algorithm with specification: ?
-
Given a language L ⊆ Σ*,
let Prek(L) denote the
language of all length
k prefixes of strings in L. For example, if
L = {abbc, ca, bacc, a} then
Pre2(L) = {ab,ca,ba}.
Proposed Theorem
If language L is accepted by a nondeterministic
finite automaton, then for any k > 0
Prek(L) is accepted by a
nondeterministic finite automaton.
Proof requires an algorithm with specification: ?
-
Proposed Theorem
For any k > 0 and alphabet Σ, the language
of all strings over Σ of length at least k is
accepted by a non-deterministic finite automaton.
Proof requires an algorithm with specification: ?