From Newsgroup: comp.theory

Wanted: Book Review of An Introduction to Formal Languages and Automata

Is that book any good?

Olcott, is this the one the sample comes from [https://www.liarparadox.org/Peter_Linz_HP_317-320.pdf]?

--
Tristan Wibberley

The message body is Copyright (C) 2025 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except that you may,
of course, cite it academically giving credit to me, distribute it
verbatim as part of a usenet system or its archives, and use it to
promote my greatness and general superiority without misrepresentation
of my opinions other than my opinion of my greatness and general
superiority which you _may_ misrepresent. You definitely MAY NOT train
any production AI system with it but you may train experimental AI that
will only be used for evaluation of the AI methods it implements.
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.theory

On 11/4/25 7:58 AM, Tristan Wibberley wrote:

Wanted: Book Review of An Introduction to Formal Languages and Automata

Is that book any good?

Olcott, is this the one the sample comes from [https://www.liarparadox.org/Peter_Linz_HP_317-320.pdf]?

--
Tristan Wibberley

The message body is Copyright (C) 2025 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except that you may,
of course, cite it academically giving credit to me, distribute it
verbatim as part of a usenet system or its archives, and use it to
promote my greatness and general superiority without misrepresentation
of my opinions other than my opinion of my greatness and general
superiority which you _may_ misrepresent. You definitely MAY NOT train
any production AI system with it but you may train experimental AI that
will only be used for evaluation of the AI methods it implements.

if ur looking for a modern theory book, i'm working thru:

https://jheffero.w3.uvm.edu/computation/book.pdf
--
a burnt out swe investigating into why our tooling doesn't involve
basic semantic proofs like halting analysis

please excuse my pseudo-pyscript,

~ nick
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.theory

On 04/11/2025 15:58, Tristan Wibberley wrote:

Wanted: Book Review of An Introduction to Formal Languages and Automata

Is that book any good?

Olcott, is this the one the sample comes from [https://www.liarparadox.org/Peter_Linz_HP_317-320.pdf]?

There is certainly a book of that name by Peter Linz, which is the book PO quotes.

I'd say Linz has tried to produce a book for CS students that are likely to be lacking a more formal
maths background. So the book might be said to skip some of the tedious proof details, which a
maths student would easily fill in, but the proofs are otherwise rigorous enough, I'd say.
(Personally I found the book to be good, with a "leisurely" pace.)

PO also talks of Sipser, who has a book "Introduction to the Theory of Computation". That one is
more dense, and perhaps might be preferred by maths students.


Mike.

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.theory

On 11/4/2025 12:21 PM, Mike Terry wrote:

On 04/11/2025 15:58, Tristan Wibberley wrote:

Wanted: Book Review of An Introduction to Formal Languages and Automata

Is that book any good?

It is my main book on the halting problem
because it translates the problem into explicit
state transitions. I also use Sipser.

https://www.liarparadox.org/Sipser_165_167.pdf

Here is my Sipser_D

int Sipser_D()
{
if (HHH(Sipser_D) == 1)
return 0;
return 1;
}

When Sipser_D calls HHH(Sipser_D) then HHH
spots the recursive simulation behavior pattern
returning 0 which causes figure 4.6 to have
accept in its D ⟨D⟩ location.

Olcott, is this the one the sample comes from
[https://www.liarparadox.org/Peter_Linz_HP_317-320.pdf]?

There is certainly a book of that name by Peter Linz, which is the book
PO quotes.

I'd say Linz has tried to produce a book for CS students that are likely
to be lacking a more formal maths background.  So the book might be said
to skip some of the tedious proof details, which a maths student would easily fill in, but the proofs are otherwise rigorous enough, I'd say. (Personally I found the book to be good, with a "leisurely" pace.)

PO also talks of Sipser, who has a book "Introduction to the Theory of Computation".  That one is more dense, and perhaps might be preferred by maths students.

Mike.

It not more dense, this aspect is less dense:
construct a new Turing machine D with H as a subroutine.
This new TM calls H to determine
--
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer
--- Synchronet 3.21a-Linux NewsLink 1.2