Problem Solving in Automata, Languages, and Complexity

86 FIN1T.E AUTOMATA Since 3(lc-l)P+P is an odd integer, and since 2”k-1 divides 2”” - 2”“-‘, we must have that 2mk-1 divides the ...

2.8 Pumping Lemmas 87 (1) Both i and j are greater than or equal to n. Then, (x: = an and x = cn and so ancn E L’. (2) The integ ...

88 FINITE AUTOMATA w Show that the set of all strings over r that represent correct tiplication, with the second mu1 t ipli .er ...

3 Context-Free Languages 3.1 Context-Free Grammars In the study of natural languages, a grammar is a set of rules that govern ho ...

90 CONTEXT-FREE LANGUAGES (2.1) We select a nonterminal symbol (a> in the sentential form and replace it by the right-hand si ...

3.1 Con text-Free Grammars 91 (or, x 3 y, if G is understood), if there exists a sequence x = x0, xl, x2,... , Xn = y of sentent ...

92 CONTEXT-FREE LANGUAGES Now, if we replace each A by either a or bb, we get a sentence of the form (a + bb)(ba + bbb)n(a + bb) ...

3.1 Context-Free Grammars 93 Solution. Using the matching approach, we need to match, in a string x E L, each b with an a which ...

94 CONTEXT-FREE LANGUAGES then d(ul) = 1 and d(uk-1) = -1 (since d(uk) = d(u) = 0). It implies that d( ua) = 0 for some i betwee ...

3.1 Context-Free Grammars 95 1 w Figure 3.1: DFA for Example 3.8. (a) Figure 3.2: Two NFA’s for Example 3.9. +J~@ 01 & Y D 0 ...

96 CONTEXT-FREE LANGUAGES We note that the NFA can be simplified into a 3-vertex labeled digraph with each edge labeled by a sin ...

3.1 Context-Free Grammars 97 Figure 3.3: Solution to Example 3.11. Thus, it is clear that L(G2) = L(G#? From the first part of t ...

98 CONTEXT-FREE LANGUAGES Show that no string in language L(G) contains substring ba, where G is the context-free grammar with ...

3.2 ExampIes of Context-Free Grammars 99 A context-free grammar G = (V, C, R, S) is said to be linear if every rule of it is of ...

100 CONTEXT-FREE LANGUAGES q-4-J = -2. It follows that for some i,^1 < - i < - n - 1, d(wi) = -1. So, W = wiv and both wi ...

3.2 Examples of Context-Free Grammars 101 Example 3.13 Find a context-free grammar for the language L = {x: E {a,b}* 1 #b(X) = 2 ...

102 CONTEXT-FREE LANGUAGES Solution. First, let us consider the simpler language L1 = { a”b”cp 1 m+ 272 = p). Based on the idea ...

3.2 Examples of Context-Free Grammars 103 First, consider L 4. A string in L4 is of the form u~~+~P, where 3(5p+4) < 57-t < ...

104 CONTEXT-FREE LANGUAGES Theorem 3.17 The class of context-free languages are closed under union, concatenation, and Kleene cl ...

3.2 Examples of Con text-Free Grammars^105 and Lz can be generated by s:! + 1 IS21 1 OSzl. Thus, we can combine the above rules ...