Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Programming-based formal languages and automata theory: design, implement, validate, and prove
Morazan M., Springer International Publishing, Cham, Switzerland, 2023. 524 pp. Type: Book (9783031439728)
Date Reviewed: Oct 24 2024

This rather difficult read introduces the programming language FSM and the programming platform DrRacket. The author asserts that it is a convenient platform to design and prove an automata-based software artifact. The 500-plus-page volume is divided into five parts: “Fundamental Concepts,” “Regular Languages,” “Context-Free Languages,” “Context-Sensitive Languages,” and “Epilogue.” Its comprehensive preface gives advice to instructors and students separately, and advises readers to first download DrRacket and FSM. However, I did not find this platform to be user friendly.

The first three chapter constitute Part 1. The first chapter introduces FSM, including syntax, functions, lists, conditional expressions, and definitions. Chapter 2 lists the required background knowledge and chapter 3 is an essay on proofs.

Chapters 4 through 9 make up Part 2. Chapter 4 defines regular expressions and their use in programming, for example, in FSM. Chapter 5 is on deterministic finite-state machines. It also highlights how FSM is used to design an artifact using deterministic finite-state machine concepts. Chapter 6 is on nondeterministic finite-state machines. It highlights how FSM is used to design an artifact using nondeterministic finite-state machine concepts. Chapter 7 is on finite-state autonomous and regular expressions, as in FSM. It also highlights how FSM is used to design an artifact using finite-state autonomous and regular expressions. Chapter 8 is on regular grammars. It also highlights how FSM is used for regular expressions. Chapter 9, “Languages That Are Not Regular,” highlights how FSM is used for nonregular expression proving.

Part 3, “Context-Free Languages,” has five chapters. Chapter 10, “Context-Free Grammars [CFGs],” defines CFGs, design expressions for CFGs, and parsing trees for CFGs. It asserts that “all regular languages [have] CFG.” Chapter 11, “Pushdown Automata [PDAs],” defines PDAs and formal expressions for PDAs, in addition to distinguishing non-PDA (NDFA) and PDA expressions. Chapter 12 establishes equivalence in PDAs and CFGs; how to build PDAs from CFGs, and vice versa, is also discussed. Chapter 13, “Properties of Context-Free Languages,” discusses such required operations as union, concatenation, the Kleene star, the pumping lemma for context-free theory, the intersection of a context-free language and a regular language, and the assertion that “context-free languages are not closed under intersection nor complement.” Chapter 14 is on deterministic PDAs. Design ideas and tests are discussed, along with formal definitions and proofs.

The next six chapters (15 through 20) discuss context-sensitive languages. Chapter 15, “Turing Machines,” starts with formal definitions of name, alphabet, and tests, along with implementation and testing for a Turing machine (L = a*), including a formal definition and proof of correctness. These are further explained for nondeterministic Turing machines and other cases, along with regular languages. Chapter 16 describes Turing machine composition, including simple common operations such as move right, move left, halt, and input/output (I/O), Turing machine composition, and the features of a programmed Turing machine. Subsequently, the universal Turing machine is defined along with how to use it. Discussions include design ideas and tests for the designs. The chapter closes with a discussion on computing with Turing machines. Chapter 17 is on Turing machine extensions. It describes multi-tape Turing machines; formal expressions for names, alphabets, and preconditions; and single-tape and multi-tape Turing machines. Chapter 18, “Context-Sensitive Grammars,” is a formal discussion of grammars for automata design programs. Chapter 19, “Church-Testing Thesis and Undesirability,” discusses what can and cannot be computed using Turing machine algorithms. Issues such as the halting problem, reduction proofs, undecidable problems about Turing machines, and undecidable problems about grammars are discussed.

Chapter 20, “Complexity,” looks at how computationally deterministic and deterministic finite-state machines are equivalent. It formally discusses the equivalence of deterministic and nondeterministic Turing machines for design and correctness proving. For defining practical solutions, a class of polynomials (P) is defined and an attempt is made to find a closed solution. The designer identifies formulae for representing and parsing inputs--this task may be quite complex. The text hints at several possible strategies while discussing the 2-satisfiability problem in P. Another goal of the complexity (theory) discussion “is to discover mathematical approaches to establish that solutions to practical problems are not in P.” For such artifacts, a class of S set of polynomials called NP is defined. Hopefully, solutions can be found.

Part 5 has only one chapter (21): “Where to Go from Here.” The author points out that the book introduces a formal approach to automata, grammars, and computing algorithms, and recommends deeper study of Chomsky normal form.

To me, the purpose of the book seems to be to convince readers of at least the following: (1) automata can be expressed through algorithms; (2) correctness of such algorithms can be proved in most cases; and (3) it is possible to develop computer programs for designing and validating automata. I’m not convinced these objectives have been achieved, as the flow of ideas between the author and the reader is hampered by the book’s organization and too much emphasis on formal mathematical expressions. For students and practicing professionals, the usefulness of the book is doubtful.

Reviewer:  Anoop Malaviya Review #: CR147830
Bookmark and Share
 
General (D.1.0 )
 
 
Automata (F.1.1 ... )
 
 
Formal Languages (F.4.3 )
 
Would you recommend this review?
yes
no
Other reviews under "General": Date
Problems in programming
Vitek A., Tvrdy I., Reinhardt R., Mohar B. (ed), Martinec M., Dolenc T., Batagelj V. (ed), John Wiley & Sons, Inc., New York, NY, 1991. Type: Book (9780471930174)
Aug 1 1992
KNOs: KNowledge acquisition, dissemination, and manipulation Objects
Tsichritzis D., Fiume E., Gibbs S., Nierstrasz O. ACM Transactions on Information Systems 5(1): 96-112, 1987. Type: Article
Nov 1 1987
Programmer perceptions of productivity and programming tools
Hanson S. (ed), Rosinski R. Communications of the ACM 28(2): 180-189, 1985. Type: Article
Jul 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy