Elements Of Computation Theory – Arindama Singh

Let L = L(G), where G = (N, Σ, R, S) be a context-free grammar. Define another context-free grammar G∗= (N, Σ, R∗, S) with R∗= R ∪{S →ε, S →SS}. Is it clear why we are doing this? In G∗you can now derive ε. Also you can derive from the first S in SS any string that can be derived in G and from the second S another such string so that their concatenation can be derived in S.

Inductively, that must give you L∗= ∪n∈NLn. Let us try to prove that G∗indeed generates L∗. Trivially, L0 = {ε} ⊆L(G∗) due to the production S →ε. Suppose that Lm ⊆L(G∗) for 0 ≤m ≤k. Let w ∈Lk+1. Then w = uv, where u ∈Lk and v ∈L. That means, we have derivations S ⇒G∗u and S ⇒G v. However, all the productions in G are also in G∗.

Thus, S ⇒G∗v. A derivation of w in G∗is S ⇒SS ⇒uS ⇒uv = w. By induction, it follows that Lk ⊆L(G∗) for every k ∈N. Thus, L∗= ∪k∈NLk ⊆ L(G∗). Conversely, whenever a nonempty string is derived in G∗, it has to be a con- catenation of strings derived in G. As L∗contains all possible concatenations of strings of L, we have L(G∗) ⊆L∗.

This completes the proof that L(G∗) = L∗. For the other two operations, let G1 = (N1, Σ1, R1, S1), G2 = (N2, Σ2, R2, S2), where N1 ∩N2  ∅, L(G1) = L1, and L(G2) = L2. Let S be a new symbol not in N1 ∪N2. Write N3 = N1 ∪N2 ∪{S} and Σ3 = Σ1 ∪Σ2. Construct Gc = (N3, Σ3, Rc, S), where Rc = R1 ∪R2 ∪{S →S1S2}.

G∪= (N3, Σ3, R∪, S), where R∪= R1 ∪R2 ∪{S →S1, S →S2}. You can now verify that L(Gc) = L1L2 and L(G∪) = L1 ∪L2. ⊓⊔ Exercise 6.10. Show that L(G∪) = L1 ∪L2 and L(Gc) = L1L2 to complete the proof of Theorem 6.3. Theorem 6.4. Intersection of two context-free languages need not be context-free and complement of a context-free language need not be context-free.

Proof. Let L1 = {aibic j : i, j ∈N} and L2 = {aib jc j : i, j ∈N}. These languages are context-free as the context-free grammar with productions S →AB, A →ε | aAb, B →ε | cB generates L1 and the context-free grammar that has productions S →AB, A →ε | aA, B →ε | bBc generates L2. But the language L1 ∩L2 = {ambmcm : m ∈N} is not context-free as you have seen in Example 6.8.

Therefore, intersection of context-free languages need not be context-free. Structure of CFLs Suppose that complement of any context-free language is context-free. Then L1, L2 are context-free.

Springer Dordrecht Heidelberg London New York British Library Cataloguing in Publication Data A catalogue record for this book is available from the British Library Library of Congress Control Number: applied for c⃝Springer-Verlag London Limited 2009 Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act of 1988, this publication may only be repro- duced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms of licences issued by the Copyright Licensing Agency.

Enquiries concerning reproduction outside those terms should be sent to the publishers. The use of registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant laws and regulations and therefore free for general use. The publisher makes no representation, express or implied, with regard to the accuracy of the information contained in this book and cannot accept any legal responsibility or liability for any errors or omissions that may be made.

Cover design: SPi Publisher Services Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com) Preface The foundation of computer science is built upon the following questions: What is an algorithm? What can be computed and what cannot be computed? What does it mean for a function to be computable? How does computational power depend upon programming constructs?

Which algorithms can be considered feasible? For more than 70 years, computer scientists are searching for answers to such ques- tions. Their ingenious techniques used in answering these questions form the theory of computation. Theory of computation deals with the most fundamental ideas of computer sci- ence in an abstract but easily understood form. The notions and techniques employed are widely spread across various topics and are found in almost every branch of com- puter science. It has thus become more than a necessity to revisit the foundation, learn the techniques, and apply them with confidence.

Overview and Goals This book is about this solid, beautiful, and pervasive foundation of computer sci- ence. It introduces the fundamental notions, models, techniques, and results that form the basic paradigms of computing. It gives an introduction to the concepts and mathematics that computer scientists of our day use to model, to argue about, and to predict the behavior of algorithms and computation.

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.

Book Information

• Unique ID: 811d3d5b08e69a9e
• File Extension: .pdf
• File Size: 3,511,652 bytes (3.349 MB)
• Title: –
• Author: Unknown
• ISBN: 9781848824966, 9781848824973
• Pages: 430
• Language: English (en)

Reading & Word Statistics

• Estimated Reading Time: 1032.06 minutes
• Total Words: 206,412
• Total Characters: 1,042,504
• Average Words per Page: 480.03
• Average Characters per Page: 2424.43

Most Frequent Words

string (942), language (925), state (893), machine (720), one (682), regular (637), let (603), set (584), input (564), show (553), languages (552), example (489), problem (469), given (434), symbol (433), states (427), number (410), also (404), time (395), first (362), following (361), function (359), dfa (350), two (339), problems (330), tape (322), strings (312), turing (305), see (297), computation (289), theorem (283), productions (283), whether (282), grammar (280), accepts (279), transition (269), use (262), construct (259), thus (257), algorithm (253), form (252), right (247), fig (245), nfa (243), iff (243), machines (240), proof (240), symbols (238), enumerable (237), initial (237), context-free (234), called (233), cfg (231), left (231), length (228), say (219), now (218), write (217), relation (210), suppose (208), alphabet (208), finite (204), computably (204), prove (201), accepting (198), accepted (197), final (195), derivation (189), production (189), stack (182), new (179), polynomial (173), decidable (173), using (171), step (170), another (168), solution (168), case (167), numbers (167), configuration (166), give (165), take (164), accept (160), pda (158), read (156), next (154), define (154), least (153), square (152), transitions (152), lemma (150), second (149), defined (148), space (147), binary (140), tree (139), used (137), expression (133), cnf (132), complexity (130).

PDF Download