 9.5.1: Describe L(G) for the grammar G = (V, VT, S, P) where V = 5a, A, B,...
 9.5.2: Describe L(G) for the grammar G = (V, VT, S, P) where V = 50, 1, A,...
 9.5.3: Describe L(G) for the grammar G = (V, VT, S, P) where V = 50, 1, A,...
 9.5.4: Describe L(G) for the grammar G = (V, VT, S, P) where V = 50, 1, A,...
 9.5.5: Find a regular grammar that generates the language of Exercise 1.
 9.5.6: Find a regular grammar that generates the language of Exercise 2.
 9.5.7: Find a regular grammar that generates the language of Exercise 3.
 9.5.8: Find a regular grammar that generates the language of Exercise 4
 9.5.9: Describe L(G) for the grammar G = (V, VT, S, P) where V = 5a, b, A,...
 9.5.10: Describe L(G) for the grammar G = (V, VT, S, P) where V = 50, 1, A,...
 9.5.11: Describe L(G) for the grammar G = (V, VT, S, P) where V = 5a, b, A,...
 9.5.12: Describe L(G) for the grammar G = (V, VT, S, P) where V = 5a, b, c,...
 9.5.13: Write the productions of the following grammars in BNF: a. G in Exe...
 9.5.14: Write the productions of the following grammars in BNF: a. G in Exe...
 9.5.15: A grammar G is described in BNF as ::= 1010 00 a. Find a regular ex...
 9.5.16: A grammar G is described in BNF as ::= 01000 1 a. Find a regular ex...
 9.5.17: Find a grammar that generates the set of all strings of wellbalanc...
 9.5.18: English words are translated into pig latin by the following two ru...
 9.5.19: A word w in V* is a palindrome if w = wR, where wR is the reverse o...
 9.5.20: a. Let L be a palindrome language (see Exercise 19). Prove that LR ...
 9.5.21: Find a regular grammar that generates the language L = 11(0 ~ 1)*.
 9.5.22: Find a regular grammar that generates the language L = (0 ~ 1)*01.
 9.5.23: Find a grammar that generates the language L = 512n 0 n 06.
 9.5.24: Find a regular expression for the language of Exercise 23. Is your ...
 9.5.25: Find a contextfree grammar that generates the language L = 50n 1n ...
 9.5.26: Find a contextfree grammar that generates the language L = 5wwR 0 ...
 9.5.27: Find a contextfree grammar that generates the language L where L c...
 9.5.28: Find a contextfree grammar that generates the language L where L c...
 9.5.29: Find a grammar that generates the language L = 502i 0 i 06.
 9.5.30: Find a grammar that generates the language L = 5ww 0 w [ 50, 16*6.
 9.5.31: Find a grammar that generates the language L = 5ww 0 w [ 50, 16*6.
 9.5.32: Find a grammar that generates the language L = 5an2 0 n 16. (By Exe...
 9.5.33: Draw parse trees for the following words: a. 111111 in the grammar ...
 9.5.34: Draw parse trees for the following words: a. 011101 in the grammar ...
 9.5.35: Consider the contextfree grammar G = (V, VT, S, P) where V = 50, 1...
 9.5.36: Ambiguity in a grammar (see Exercise 35) that describes a programmi...
 9.5.37: Show that for any contextfree grammar G there exists a contextfre...
 9.5.38: Following is the pumping lemma for contextfree languages. Let L be...
Solutions for Chapter 9.5: Formal Languages
Full solutions for Mathematical Structures for Computer Science  7th Edition
ISBN: 9781429215107
Solutions for Chapter 9.5: Formal Languages
Get Full SolutionsThis expansive textbook survival guide covers the following chapters and their solutions. Mathematical Structures for Computer Science was written by and is associated to the ISBN: 9781429215107. Since 38 problems in chapter 9.5: Formal Languages have been answered, more than 21743 students have viewed full stepbystep solutions from this chapter. Chapter 9.5: Formal Languages includes 38 full stepbystep solutions. This textbook survival guide was created for the textbook: Mathematical Structures for Computer Science, edition: 7.

Associative Law (AB)C = A(BC).
Parentheses can be removed to leave ABC.

Augmented matrix [A b].
Ax = b is solvable when b is in the column space of A; then [A b] has the same rank as A. Elimination on [A b] keeps equations correct.

Big formula for n by n determinants.
Det(A) is a sum of n! terms. For each term: Multiply one entry from each row and column of A: rows in order 1, ... , nand column order given by a permutation P. Each of the n! P 's has a + or  sign.

CayleyHamilton Theorem.
peA) = det(A  AI) has peA) = zero matrix.

Characteristic equation det(A  AI) = O.
The n roots are the eigenvalues of A.

Complex conjugate
z = a  ib for any complex number z = a + ib. Then zz = Iz12.

Conjugate Gradient Method.
A sequence of steps (end of Chapter 9) to solve positive definite Ax = b by minimizing !x T Ax  x Tb over growing Krylov subspaces.

Dot product = Inner product x T y = XI Y 1 + ... + Xn Yn.
Complex dot product is x T Y . Perpendicular vectors have x T y = O. (AB)ij = (row i of A)T(column j of B).

Echelon matrix U.
The first nonzero entry (the pivot) in each row comes in a later column than the pivot in the previous row. All zero rows come last.

Graph G.
Set of n nodes connected pairwise by m edges. A complete graph has all n(n  1)/2 edges between nodes. A tree has only n  1 edges and no closed loops.

Jordan form 1 = M 1 AM.
If A has s independent eigenvectors, its "generalized" eigenvector matrix M gives 1 = diag(lt, ... , 1s). The block his Akh +Nk where Nk has 1 's on diagonall. Each block has one eigenvalue Ak and one eigenvector.

Multiplier eij.
The pivot row j is multiplied by eij and subtracted from row i to eliminate the i, j entry: eij = (entry to eliminate) / (jth pivot).

Normal equation AT Ax = ATb.
Gives the least squares solution to Ax = b if A has full rank n (independent columns). The equation says that (columns of A)·(b  Ax) = o.

Normal matrix.
If N NT = NT N, then N has orthonormal (complex) eigenvectors.

Nullspace matrix N.
The columns of N are the n  r special solutions to As = O.

Orthonormal vectors q 1 , ... , q n·
Dot products are q T q j = 0 if i =1= j and q T q i = 1. The matrix Q with these orthonormal columns has Q T Q = I. If m = n then Q T = Q 1 and q 1 ' ... , q n is an orthonormal basis for Rn : every v = L (v T q j )q j •

Reflection matrix (Householder) Q = I 2uuT.
Unit vector u is reflected to Qu = u. All x intheplanemirroruTx = o have Qx = x. Notice QT = Q1 = Q.

Special solutions to As = O.
One free variable is Si = 1, other free variables = o.

Standard basis for Rn.
Columns of n by n identity matrix (written i ,j ,k in R3).

Vector space V.
Set of vectors such that all combinations cv + d w remain within V. Eight required rules are given in Section 3.1 for scalars c, d and vectors v, w.