1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 31

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 31)

Deterministic finite-state transducers were introduced in Problem 2.1.4.Show that if L is context-free and I is computed by a deterministic finitestate transducer, then(a) I[L] is context-free;(b)1 [L1is context-free.r3.5.12. Develop a version of the Pumping Theorem for context-free languages inwhich the length of the "pumped part" is as long as possible.3.5.13. Let M1 and M2 be pushdown automata. Show how to construct pushdown automata accepting L(M1 ) UL(M2 ), L(M1 )L(M2 ), and L(Md", thusproviding another proof of Theorem 3.5.1.3.5.14. Which of the following languages are context-free? Explain briefly in eachcase.(a) {ambnc p : m = nor n = p or m = p}(b) {ambncp : m ¥- nor n ¥- p or m ¥- p}Chapter 3: CONTEXT-FREE LANGUAGES150(c) {ambnc p : Tn = nand n = p and Tn = p}(d) {w E {a, b, c}': W does not contain equal numbers of occurrences ofa, b, and c}(e) {w E {a, b}' : W = WI W2 ...

Wm for some Tn ? 2 and WI, ... ,W m suchthat IWII = IW21 = ... = Iwml? 2}3.5.15. Suppose that L is context-free and R is regular. Is L- R necessarily contextfree? What about R - L? Justify your answers.3.6ALGORITHMS FOR CONTEXT-FREE GRAMMARSIn this section we consider the computational problems related to context-freelanguages, we develop algorithms for these problems, and we analyze their complexity.

All in all, we establish the following results.Theorem 3.6.1: (a) There is a polynomial algorithm which, given a context-freegrammar, constructs an equivalent pushdown automaton.(b) There is a polynomial algorithm which, given a pushdown automaton, constructs an equivalent context-free grammar.(c) There is a polynomial algorithm which, given a context-free grammar G anda string x, decides whether x E L( G).It is instructive to compare Theorem 3.6.1 with the corresponding statementsummarizing the algorithmic aspects of finite automata (Theorem 2.6.1). To besure, there are certain similarities: in both cases there are algorithms whichtransform acceptors to generators and vice versa -then finite automata to regular expressions and back, now pushdown automata to context-free grammarsand back. But the differences are perhaps more striking.

First, in Theorem 2.6.1there was no need for an analog of part (c) above, since regular languages are represented in terms of an efficient algorithm for deciding precisely the membershipquestion in (c): a deterministic finite automaton. In contrast, for context-freelanguages we have so far introduced only non-algorithmic, nondeterministic acceptors -pushdown automata.

In order to establish part (c), we show in thenext subsection that for any context-free language we can construct a deterministic acceptor; the construction is rather indirect and sophisticated, and theresulting algorithm, although polynomial, is no longer linear in the length of theinput.A second major difference between Theorem 2.6.1 and Theorem 3.6.1 isthat in the present case we do not mention any algorithms for testing whethertwo given context-free grammars (or two pushdown automata) are equivalent;neither do we claim that there are algorithms for minimizing the number of statesin a pushdown automaton.

We shall see in Chapter 5 that such questions about1513.6: Algorithms for Context-Free Grammarscontext-free grammars and pushdown automata are not amenable to solution byany algorithm -however inefficient!The Dynamic Programming AlgorithmWe turn now to proving part (c) of the Theorem (parts (a) and (b) are straightforward consequences of the constructions in the proofs of the Lemmata 3.4.1and 3.4.2). Our algorithm for deciding context-free languages is based on auseful way of "standardizing" context-free grammars.Definition 3.6.1: A context-free grammar G =Chomsky normal form if R ~ (V - ~) X V 2 .(V,~,R, S) is said to be inIn other words, the right-hand side of a rule in a context-free grammarin Chomsky normal form must have length two.

Notice that no grammar inChomsky normal form would be able to produce strings of length less than two,such as a, b, or e; therefore, context-free languages containing such strings cannotbe generated by grammars in Chomsky normal form. However, the next resultstates that this is the only loss of generality that comes with Chomsky normalform:Theorem 3.6.2: For any context-free grammar G there is a context-free grammar G' 'in Chomsky normal form such that L( G') = L( G) - (~ U {e }). Furthermore, the construction of G' can be carried out in time polynomial in the size ofG.In other words, G' generates exactly the strings that G does, with thepossible exception of strings of length less than two -since G' is in Chomskynormal form, we know that it cannot generate such strings.Proof: We shall show how to transform any given context-free grammar G =(V,~, R, S) into a context-free grammar in Chomsky normal form.

There arethree ways in which the right-hand side of a rule A --+ x may violate the constraints of Chomsky normal form: long rules (those whose right-hand side haslength three or more), e-rules (of the form A --+ e), and short rules (of the formA --+ a or A --+ B). We shall show how to remove these violations one by one.We first deal with the long rules of G. Let A --+ B 1 B 2 •.. Bn E R, whereB 1, ... ,Bn E V and n 2. 3. We replace this rule with n - 1 new rules, namely:152Chapter 3: CONTEXT-FREE LANGUAGESwhere AI, ...

,A n - 2 are new nonterminals, not used anywhere else in the grammar. Since the rule A --+ B 1 B 2 •.. Bn can be simulated by the newly insertedrules, and this is the only way in which the newly added rules can be used,it should be clear that the resulting context-free grammar is equivalent to theoriginal one. We repeat this for each long rule of the grammar. The resultinggrammar is equivalent to the original one, and has rules with right-hand sidesof length two or less.Example 3.6.1: Let us take the grammar generating the set of balanced parentheses, with rules S --+ SS,S --+ (S), S --+ e. There is only one long rule,S --+ (S).

It is replaced by the two rules S --+ (SI and SI --+ S).¢We must next take on the e-rules. To this end, we first determine the setof erasable nonterminalsE= {AE V - ~ : A::::}*e},that is, the set of all nonterminals that may derive the empty string. This isdone by a simple closure calculation:E:= 0while there is a rule A --+ a withA ~ E do add A to E.QE E* andOnce we have the set E, we delete from G all e-rules, and repeat the following: For each rule of the form A --+ Be or A --+ e B with BEE and e E V, weadd to the grammar the rule A --+ e.

Any derivation in the original grammarcan be simulated in the new, and vice versa -with one exception: e cannot bederived in the language any longer, since we may have omitted the rule S --+ eduring this step. Fortunately, the statement of the Theorem allows for thisexclusion.Example 3.6.1 (continued): Let us continue from the grammar with rulesS --+ SS,S --+ (SI,SI --+ S),S --+ e.We start by computing the set E of vanishing nonterminals: Initially E = 0;then E = is}, because of the rule S --+ e; and this is the final value of E. Weomit from the grammar the e-rules (of which there is only one, S --+ e), and addvariants of all rules with an occurrence of S, with that occurrence omitted. Thenew set of rules is3.6: Algorithms for Context-Free Grammars153The rule 5 --+ 5 was added because of the rule 5 --+ 55 with 5 E E; it is ofcourse useless and can be omitted.

The rule 51 --+) was added because of therule 51 --+ 5) with 5 E E.For example, the derivation in the original grammar5::::} 55 => 5(5) => 50 => ()can now simulated by-omitting the 5 => 55 part, since the first 5 would be eventually erased- andfinally-using the 51 =» rule to anticipate the erasing of the 5 in the rule 51 => 5).¢Our grammar now has only rules whose right-hand sides have length oneand two. We must next get rid of the short rules, those with right-hand sideswith length one. We accomplish this as follows: For each A E V we compute,again by a simple closure algorithm, the set D(A) of symbols that can be derivedfrom A in the grammar, D(A) = {B E v: A =>* B}, as follows:D(A):={A}while there is a rule B -+ G with B E D(A) andG ~ D(A) do add G to D(A).Notice that for all symbols A, A E D(A); and if a is a terminal, thenD(a)= {a}.In our third and final step of the transformation of our grammar to one inChomsky normal form, we omit all short rules from the grammar, and we replaceeach rule of the form A --+ BG with all possible rules of the form A --+ B'G'where B' E D(B) and G' E D( G).

Such a rule simulates the effect of the originalrule A --+ BG, with the sequence of short rules that produce B' from B and G'from G. Finally, we add the rules 5 --+ BG for each rule A --+ BG such thatA E D(5) - {5}.Again, the resulting grammar is equivalent to the one before the omissionof the short rules, since the effect of a short rule is simulated by "anticipating"its use when the left-hand side first appears in the derivation (if the left-handside is 5, and thus it starts the derivation, the rules 5 --+ BG added in the lastpart of the construction suffice to guarantee equivalence).

Характеристики

Список файлов решённой задачи