Software Engineering Body of Knowledge (v3) (2014) (811503), страница 76
Текст из файла (страница 76)
Example of an FSMFor example, Figure 14.21 illustrates an FSMwith S0 as the start state and S1 as the final state.Here, S = {S0, S1, S2}; I = {0, 1}; O = {2, 3}; f(S0,0) = S2, f(S0, 1) = S1, f(S1, 0) = S2, f(S1, 1) = S2, f(S2,0) = S2, f(S2, 1) = S0; g(S0, 0) = 3, g(S0, 1) = 2, g(S1,0) = 3, g(S1, 1) = 2, g(S2, 0) = 2, g(S2, 1) = 3.Input01S2S1S2S2CurrentStateS0S1S2S2S0(a)CurrentStateS0S1S2OutputInput01323223StateInput01S2S1S2S2S2S0(b)Figure 14.22. Tabular Representation of an FSM[1*, c13]The grammar of a natural language tells uswhether a combination of words makes a validsentence. Unlike natural languages, a formal language is specified by a well-defined set of rules forsyntaxes.
The valid sentences of a formal languagecan be described by a grammar with the help ofthese rules, referred to as production rules.A formal language is a set of finite-lengthwords or strings over some finite alphabet, anda grammar specifies the rules for formation ofthese words or strings. The entire set of wordsthat are valid for a grammar constitutes the language for the grammar. Thus, the grammar G isany compact, precise mathematical definition of alanguage L as opposed to just a raw listing of allof the language’s legal sentences or examples ofthose sentences.A grammar implies an algorithm that wouldgenerate all legal sentences of the language.There are different types of grammars.A phrase-structure or Type-0 grammar G = (V,T, S, P) is a 4-tuple in which:• V is the vocabulary, i.e., set of words.• T ⊆ V is a set of words called terminals.• S ∈ N is a special word called the startsymbol.• P is the set of productions rules for substituting one sentence fragment for another.There exists another set N = V − T of wordscalled nonterminals.
The nonterminals representconcepts like noun. Production rules are appliedon strings containing nonterminals until no morenonterminal symbols are present in the string.The start symbol S is a nonterminal.14-16 SWEBOK® Guide V3.0The language generated by a formal grammarG, denoted by L(G), is the set of all strings overthe set of alphabets V that can be generated, starting with the start symbol, by applying production rules until all the nonterminal symbols arereplaced in the string.For example, let G = ({S, A, a, b}, {a, b}, S, {S→ aA, S → b, A → aa}). Here, the set of terminals are N = {S, A}, where S is the start symbol.The three production rules for the grammar aregiven as P1: S → aA; P2: S → b; P3: A → aa.Applying the production rules in all possibleways, the following words may be generatedfrom the start symbol.S → aA → aaa S → b (using P1 on start symbol)(using P3)(using P2 on start symbol)Nothing else can be derived for G.
Thus, thelanguage of the grammar G consists of only twowords: L(G) = {aaa, b}.8.1. Language RecognitionFormal grammars can be classified according to thetypes of productions that are allowed. The Chomsky hierarchy (introduced by Noam Chomsky in1956) describes such a classification scheme.Figure 14.23. Chomsky Hierarchy of GrammarsAs illustrated in Figure 14.23, we infer the following on different types of grammars:1.Every regular grammar is a context-freegrammar (CFG).2.Every CFG is a context-sensitive grammar(CSG).3.Every CSG is a phrase-structure grammar(PSG).Context-Sensitive Grammar: All fragments inthe RHS are either longer than the correspondingfragments in the LHS or empty, i.e., if b → a, then|b| < |a| or a = ∅.A formal language is context-sensitive if a context-sensitive grammar generates it.Context-Free Grammar: All fragments in theLHS are of length 1, i.e., if A → a, then |A| = 1for all A ∈ N.The term context-free derives from the fact thatA can always be replaced by a, regardless of thecontext in which it occurs.A formal language is context-free if a contextfree grammar generates it.
Context-free languages are the theoretical basis for the syntax ofmost programming languages.Regular Grammar. All fragments in the RHSare either single terminals or a pair built by aterminal and a nonterminal; i.e., if A → a, theneither a ∈ T, or a = cD, or a = Dc for c ∈ T, D ∈ N.If a = cD, then the grammar is called a rightlinear grammar.
On the other hand, if a = Dc, thenthe grammar is called a left linear grammar. Boththe right linear and left linear grammars are regular or Type-3 grammar.The language L(G) generated by a regulargrammar G is called a regular language.A regular expression A is a string (or pattern)formed from the following six pieces of information: a ∈ S, the set of alphabets, e, 0 and theoperations, OR (+), PRODUCT (.), CONCATENATION (*).
The language of G, L(G) is equal toall those strings that match G, L(G) = {x ∈ S*|xmatches G}.For any a ∈ S, L(a) = a; L(e) = {ε}; L(0) = 0.+ functions as an or, L(A + B) = L(A) ∪ L(B).. creates a product structure, L(AB) = L(A) .L(B).* denotes concatenation, L(A*) = {x1x2…xn |xi ∈ L(A) and n ³ 0}For example, the regular expression (ab)*matches the set of strings: {e, ab, abab, ababab,abababab, …}.Mathematical Foundations 14-17For example, the regular expression (aa)*matches the set of strings on one letter a that haveeven length.For example, the regular expression (aaa)* +(aaaaa)* matches the set of strings of length equalto a multiple of 3 or 5.9. Numerical Precision, Accuracy, and Errors[2*, c2]The main goal of numerical analysis is todevelop efficient algorithms for computing precise numerical values of functions, solutions ofalgebraic and differential equations, optimizationproblems, etc.A matter of fact is that all digital computers canonly store finite numbers.
In other words, thereis no way that a computer can represent an infinitely large number—be it an integer, rationalnumber, or any real or all complex numbers (seesection 10, Number Theory). So the mathematicsof approximation becomes very critical to handleall the numbers in the finite range that a computercan handle.Each number in a computer is assigned a location or word, consisting of a specified number ofbinary digits or bits. A k bit word can store a totalof N = 2k different numbers.For example, a computer that uses 32 bit arithmetic can store a total of N = 232 ≈ 4.3 × 109 different numbers, while another one that uses 64bits can handle N’ = 264 ≈ 1.84 × 1019 differentnumbers.
The question is how to distribute theseN numbers over the real line for maximum efficiency and accuracy in practical computations.One evident choice is to distribute them evenly,leading to fixed-point arithmetic. In this system,the first bit in a word is used to represent a signand the remaining bits are treated for integer values. This allows representation of the integersfrom 1 − ½N, i.e., = 1 − 2k−1 to 1. As an approximating method, this is not good for nonintegernumbers.Another option is to space the numbers closelytogether—say with a uniform gap of 2−n—and sodistribute the total N numbers uniformly over theinterval −2−n−1N < x ≤ 2−n−1N.
Real numbers lyingbetween the gaps are represented by either rounding (meaning the closest exact representative)or chopping (meaning the exact representativeimmediately below —or above, if negative—thenumber).Numbers lying beyond the range must be represented by the largest (or largest negative) numberthat can be represented. This becomes a symbolfor overflow. Overflow occurs when a computation produces a value larger than the maximumvalue in the range.When processing speed is a significant bottleneck, the use of the fixed-point representationsis an attractive and faster alternative to the morecumbersome floating-point arithmetic most commonly used in practice.Let’s define a couple of very important terms:accuracy and precision as associated with numerical analysis.Accuracy is the closeness with which a measured or computed value agrees with the true value.Precision, on the other hand, is the closenesswith which two or more measured or computedvalues for the same physical substance agree witheach other.
In other words, precision is the closeness with which a number represents an exactvalue.Let x be a real number and let x* be an approximation. The absolute error in the approximationx* ≈ x is defined as | x* − x |. The relative erroris defined as the ratio of the absolute error to thesize of x, i.e., |x* − x| / | x |, which assumes x ¹ 0;otherwise, relative error is not defined.For example, 1000000 is an approximation to1000001 with an absolute error of 1 and a relativeerror of 10−6, while 10 is an approximation of 11with an absolute error of 1 and a relative error of0.1.
Typically, relative error is more intuitive andthe preferred determiner of the size of the error.The present convention is that errors are always≥ 0, and are = 0 if and only if the approximationis exact.An approximation x* has k significant decimal digits if its relative error is < 5 × 10−k−1. Thismeans that the first k digits of x* following itsfirst nonzero digit are the same as those of x.Significant digits are the digits of a number thatare known to be correct.
In a measurement, oneuncertain digit is included.For example, measurement of length witha ruler of 15.5 mm with ±0.5 mm maximum14-18 SWEBOK® Guide V3.0allowable error has 2 significant digits, whereasa measurement of the same length using a caliperand recorded as 15.47 mm with ±0.01 mm maximum allowable error has 3 significant digits.10. Number Theory[1*, c4]Number theory is one of the oldest branchesof pure mathematics and one of the largest. Ofcourse, it concerns questions about numbers,usually meaning whole numbers and fractional orrational numbers. The different types of numbersinclude integer, real number, natural number,complex number, rational number, etc.10.1. DivisibilityLet’s start this section with a brief description ofeach of the above types of numbers, starting withthe natural numbers.Natural Numbers. This group of numbers startsat 1 and continues: 1, 2, 3, 4, 5, and so on.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
