Linear algebra done wrong

Cover......Page 1
Contents......Page 8
Preface......Page 14
Acknowledgements......Page 18
List of implementations......Page 20
List of symbols......Page 22
List of mathematical models......Page 24
List of language families......Page 26
Part I. Basic mathematical concepts......Page 30
  1.1 Sets......Page 32
  1.2 Sequences......Page 39
  1.3 Formal languages......Page 40
  2.1 Relations......Page 50
  2.2 Functions......Page 54
  3.1 Directed graphs......Page 58
  3.2 Trees......Page 59
Part II. Classical models for languages and computation......Page 64
  4.1 Rewriting systems......Page 66
  4.2 Language-defining models......Page 71
  5.1 Mathematical elements of finite automata......Page 76
   5.1.1 How to specify finite automata......Page 77
    5.1.1.3 State diagram......Page 78
    5.1.1.4 Formal description......Page 79
  5.2 Finite automata that always read......Page 82
  5.3 Determinism......Page 89
  5.4 Reduction and minimization......Page 100
  5.5 Regular expressions......Page 104
  6.1 Mathematical elements of context-free grammars......Page 116
   6.2.1 Leftmost derivations......Page 123
   6.2.3 Derivation trees......Page 125
   6.2.4 Ambiguity......Page 127
  6.3 Useless symbols and their elimination......Page 131
  6.4 Erasing rules and their elimination......Page 138
  6.5 Single rules and their elimination......Page 143
  6.6 Chomsky normal form......Page 147
  6.7 Left recursion and its removal......Page 152
   6.7.1 Direct left recursion and its elimination......Page 153
   6.7.2 Left recursion and its elimination......Page 154
  6.8 Greibach normal form......Page 161
  7.1 Pushdown automata......Page 168
  7.2 Pushdown automata and context-free grammars are equivalent......Page 175
  7.3 Three types of acceptance by pushdown automata......Page 179
  7.4 Determinism......Page 181
  8.1 Turing machines and their languages......Page 188
  8.2 Determinism......Page 196
   8.3.1 Turing machine codes......Page 200
   8.3.2 Construction of universal Turing machines......Page 205
  9.1 Functions computed by Turing machines......Page 208
  9.2 Mathematical theory of computability: an introduction......Page 213
  10.1 Turing deciders......Page 220
   10.2.1 Decidable problems for finite automata......Page 223
   10.2.2 Decidable problems for context-free grammars......Page 225
  10.3 Undecidability: diagonalization......Page 227
  10.4 Undecidability: reduction......Page 230
  10.5 Undecidability: a general approach to reduction......Page 233
  10.6 Computational complexity......Page 237
   10.6.1 Time complexity......Page 238
   10.6.2 Space complexity......Page 240
Part III. Alternative models for languages and computation......Page 242
  11.1 Tightly context-dependent grammars......Page 244
  11.2 Loosely context-dependent grammars......Page 261
   12.1.1 Definitions and examples......Page 322
   12.2.1 Definitions and examples......Page 324
   12.3.1 Definitions and examples......Page 328
   12.3.3 Even matrix grammars......Page 330
    12.3.3.1 Definitions and examples......Page 331
    12.3.3.2 Generative power......Page 334
   12.4.1 Definitions and examples......Page 342
   12.5.1 Self-regulating automata......Page 345
    12.5.2.1 Definitions and examples......Page 346
    12.5.2.2 Accepting power......Page 348
    12.5.2.3 n-Turn first-move self-regulating finite automata......Page 349
    12.5.2.4 Language families accepted by n-first-SFAs and n-all-SFAs......Page 359
    12.5.3.1 Definitions......Page 361
    12.5.3.2 Accepting power......Page 362
   12.5.6 Finite automata regulated by control languages......Page 364
    12.5.6.1 Definitions......Page 365
    12.5.6.2 Conversions......Page 366
    12.5.6.4 Context-free-controlled finite automata......Page 368
    12.5.6.5 Program-controlled finite automata......Page 369
    12.5.7.1 Definitions......Page 378
    12.5.7.2 Regular-controlled pushdown automata......Page 379
    12.5.7.3 Linear-controlled pushdown automata......Page 380
    12.5.7.4 One-turn linear-controlled pushdown automata......Page 385
   12.5.8 Self-reproducing pushdown transducers......Page 389
   12.5.9 Definitions......Page 390
   12.5.10 Results......Page 391
   13.1.1 Definitions and examples......Page 396
   13.1.3 Normal forms......Page 400
   13.1.4 Reduction......Page 402
   13.1.5 Economical transformations......Page 414
  13.2 Totally parallel grammars......Page 421
    13.2.1.1 Definitions......Page 422
    13.2.1.2 Generative power......Page 423
    13.2.2.1 Definitions and examples......Page 429
    13.2.2.2 Generative power and reduction......Page 430
    13.2.3.1 Definitions......Page 448
    13.2.3.2 Generative power and reduction......Page 449
   13.2.4 Left random context ET0L grammars......Page 462
    13.2.4.1 Definitions and examples......Page 463
    13.2.4.2 Generative power and reduction......Page 465
  13.3 Multigenerative grammar systems and parallel computation......Page 478
   13.3.1 Multigenerative grammar systems......Page 479
   13.3.2 Leftmost multigenerative grammar systems......Page 495
  14.1 Sequential jumping grammars......Page 508
  14.2 Parallel jumping grammars......Page 523
   14.2.1 Definitions......Page 525
    14.2.2.1 Jumping derivation mode 1......Page 527
    14.2.2.2 Jumping derivation mode 2......Page 529
    14.2.2.3 Jumping derivation mode 3......Page 537
    14.2.2.4 Jumping derivation mode 4......Page 540
    14.2.2.5 Jumping derivation mode 5......Page 544
    14.2.2.6 Jumping derivation mode 6......Page 546
    14.2.2.7 Jumping derivation mode 7......Page 547
    14.2.2.8 Jumping derivation mode 8......Page 551
    14.2.2.9 Jumping derivation mode 9......Page 552
  14.3 Jumping automata......Page 553
   14.3.1 Definitions and examples......Page 555
   14.3.2 Properties......Page 556
    14.3.2.1 Relations with well-known language families......Page 559
    14.3.2.2 Closure properties......Page 560
    14.3.2.3 Decidability......Page 563
    14.3.2.4 An infinite hierarchy of language families......Page 565
    14.3.2.5 Left and right jumps......Page 566
    14.3.2.6 A variety of start configurations......Page 567
    14.3.2.7 Relations between jumping automata and jumping grammars......Page 569
    14.3.2.8 A summary of open problems......Page 571
  15.1 Basic model......Page 574
   15.1.1 Definitions and examples......Page 575
   15.1.2 Accepting power......Page 576
   15.1.3 Open problems......Page 584
  15.2 Restricted versions......Page 585
   15.2.2 Results......Page 586
   15.2.3 Open problems......Page 591
Part IV. Applications......Page 592
  16.1 Applications in computational linguistics: general comments......Page 594
  16.2 Applications in computational biology: general comments......Page 596
 17 Applications in syntax analysis: programming languages......Page 598
  17.1 General parsers......Page 599
   17.1.1 Syntax specified by context-free grammars......Page 600
   17.1.2 Top-down parsing......Page 602
   17.1.3 Bottom-up parsing......Page 605
   17.2.1 Predictive sets and LL grammars......Page 611
   17.2.2 LL grammars......Page 618
   17.2.4 Predictive recursive-descent parsing......Page 620
   17.2.5 Predictive table-driven parsing......Page 626
   17.2.6 Handling errors......Page 632
  17.3 Bottom-up parsers......Page 634
   17.3.2 Operator-precedence parser......Page 635
   17.3.3 Construction of operator-precedence parsing table......Page 643
   17.3.4 Handling errors......Page 644
   17.3.5 Operator-precedence parsers for other expressions......Page 648
   17.3.7 LR parsing algorithm......Page 650
   17.3.8 Construction of the LR table......Page 659
   17.3.9 Handling errors in LR parsing......Page 672
  17.4 Syntax-directed translation: an implementation......Page 675
   18.1.1 Introduction by way of examples......Page 690
   18.1.2 Terminology......Page 692
   18.1.4 Personal pronouns......Page 693
  18.2 Transformational scattered context grammars......Page 695
  18.3 Scattered context in English syntax......Page 697
   18.3.1 Clauses with neither and nor......Page 698
   18.3.2 Existential clauses......Page 699
   18.3.3 Interrogative clauses......Page 700
   18.3.4 Question tags......Page 702
   18.3.5 Generation of grammatical sentences......Page 704
  19.1 Applications......Page 708
   19.1.1 Death......Page 711
   19.1.2 Degeneration......Page 712
  19.2 Implementation......Page 715
Part V. Conclusion......Page 722
  20.1 Summary of the book......Page 724
  20.2 Latest trends and open problems......Page 727
   20.3.1 Grammars......Page 729
   20.3.2 Automata......Page 730
  References......Page 731
Index......Page 750
Back Cover......Page 761