Pumping, with or without choice⋆ - nus computing

img
Pdf Available

19 pages - 342 KB

By a hobor — wan yik. on block pumpable languages. theoretical computer science, 2016. 5. noam chomsky. on certain formal properties of grammars. information and.

DownloadPrintView FileLoad Full
/ 19
60%
Table of contents
/ 19
60%

Document in text mode:

Pumping, With or Without Choice?Aquinas Hobor1 2, Elaine Li1, and Frank Stephan2 31 Yale-NUS [email protected] School of Computing, National University of Singapore{hobor, fstephan}@comp.nus.edu.sg3 Department of Mathematics, National University of SingaporeAbstract. We present the first machine-checked formalization of Jaffeand Ehrenfeucht, Parikh and Rozenberg’s (EPR) pumping lemmas in theCoq proof assistant. We formulate regularity in terms of finite derivatives,and prove that both Jaffe’s pumping property and EPR’s block pumpingproperty precisely characterize regularity. We illuminate EPR’s classicalproof that the block cancellation property implies regularity, and discoverthat—as best we can tell—their proof relies on the Axiom of Choice. Weprovide a new proof which eliminates the use of Choice. We explicitlyconstruct a function which computes block cancelable languages fromwell-formed short languages.Keywords: Pumping lemmas · Axiom of Choice · Coq1 OverviewPum...

Load more Show less

Relevant files:

  • Why everyone should have to learn computer programming
    img
    Pdf Available

    3 pages - 391 KB

    By j woodward · 2016 · cited by 4 — lecturer in computer science, university ... there are many computer languages for different purposes. ... but just as noam chomsky's.

    5047
  • Formal grammars and languages
    img
    Pdf Available

    40 pages - 210.5 KB

    Department of computer science ... noam chomsky in the 1950s, when he attempted to give a precise ... arising in many computer science applications.

    5259
  • Beyond positivism in computer science
    img
    Pdf Available

    6 pages - 149.6 KB

    By m luczak-rösch · 2013 · cited by 2 — science. author keywords. computer science; web science; philosophy;. positivism; modeling; engineering; ... [8] where he discusses a speech of noam chomsky.

    5422
  • Dear mr. president - people @ eecs at uc berkeley
    img
    Pdf Available

    4 pages - 86 KB

    Stuart russell, smith-zadeh professor of computer science, university of ... noam chomsky, institute professor emeritus, mit; national academy of sciences.

    8433
  • Introduction to automata theory
    img
    Pdf Available

    25 pages - 634.5 KB

    A fundamental question in computer science: ... alan turing (1912-1954). ▫ father of modern computer. science ... noam chomsky proposes the.

    6818
  • Professor smith noam chomsky edmund clarke stephen cook shafi ...
    img
    Pdf Available

    1 page - 523 KB

    Latex tikzposter. computer science heroes of chair vii. match then check. professor. smith. generic natural. science. noam. chomsky. edmund. clarke. stephen.

    9006

Topics related: