f:{a,b}* → NGive the values of each of the following expressions, or "error" if the function's argument is outside of its domain:
f(w) = 2|w|
f:N x Z → ZGive the values of each of the following expressions, or "error" if the function's argument is outside of its domain:
f(a,b) = a - b
f:Σ* x Σ → {true,false}Give the values of each of the following expressions, or "error" if the function's argument is outside of its domain:
f(w,x) = { false if w = e true if x is the first character of w false if x isn't the first character of w
M' = (Q,Σ,δ,s,W'), where W' = Q - WFrom our informal discussions on this algorithm, it should be clear that it does what it's supposed to, i.e. that it produces a machine accepting the complement language. A strictly formal proof relies on the concept of configuation, which we'll discuss later. On the other hand, hopefully this algorithm is so obviously correct that no further proof is needed.
The set of all (a,b), which are pairs of natural numbers, such that a + b = 1000.Essentially, the form of these expressions is {A | B} where A defines the set from which you're choosing objects, the | means "such that", and the B gives a criterion for selecting which objects will actually end up in your set. People are usually pretty free-wheeling about what goes in the A and B, as long as it's clear what set's getting constructed. The big thing to remember, is that in A you're also giving a name or pattern representing a random object which you'll refer to in B --- like I did with (a,b) in the above example.
Problems:
{w ∈ {I,J,K}* | |w| = 10}This reads "the set of all strings w over {I,J,K} such that the length of w is 10".
{w ∈ {0,1}* | w = wR}This reads "the set of all strings w over {0,1} such that w equals w reversed.
s:Z → ZThe prototype you should already know. The definition says that for any x from the function's domain, the function produces x+1.
s(x) → x+1
Often we end up breaking things up into cases when we define functions. For example, we might give the following definition for the "signed successor function" ss.
As I said before, you get a fair amount of flexibility in how you define these things. Here's an example defining a function f that takes a string and concatenates it with its reverse, with the hitch that if the string has odd length, the last character isn't doubled up in the result string. For example: f(ab) = abba, but f(abb) = abbba. Let Σ = {a,b}. We'll define f in a few different ways:
ss:Z → Z ss(x) →
{ x+1 if x > 0 x-1 if x < 0 x if x = 0
f:Σ* → Σ* f(e) → e f(wa) →
w∈Σ*, a ∈ Σ
{ waaw if |wa| even waw if |wa| odd
f:Σ* → Σ* f(a1a2a3...ak) →
{ a1a2a3...akakak-1ak-2...a1 if k even a1a2a3...akak-1ak-2...a1 if k odd
M = (Q,Σ,δ,s,W), whereOnce again, a formal proof that this algorithm really constructs a machine accepting L(M1) ∩ L(M2) will have to wait. We're familiar enough with the idea of this algorithm that we probably don't need any more convincing.
- Q = Q1 x Q2
- δ:Q x Σ → Q
&delta((q,p),a) → (δ(q,a),δ(p,a))- s = (s1,s2)
- W = W1 x W2