Post History
#2: Post edited
by
WheatWizard
·
2026-02-21T04:21:09Z (7 months ago)
- The key fact here is that regular languages are exactly the languages which can be decided by a computer with constant memory. This is basically the definition of a finite state automaton.
From here it is easy to see these facts. You've already basically observed this for union, but complementation and intersection are not difficult.* Intersection: A computer can recognize a regular language with constant memory, and it can negate its output with constant memory.* Union: If two languages can be recognized with constant memory we can run both those programs (in parallel or serially) and take the logical and of the results. This takes at most constant+constant=constant memory.
- The key fact here is that regular languages are exactly the languages which can be decided by a computer with constant memory. This is basically the definition of a finite state automaton.
- From here it is easy to see these facts. You've already observed this for union, but complementation and intersection are not difficult.
- * Complement: A computer can recognize a regular language with constant memory, and it can negate its output with constant memory.
- * Intersection: If two languages can be recognized with constant memory we can run both those programs (in parallel or serially) and take the logical and of the results. This takes at most constant+constant=constant memory.
#1: Initial revision
by
WheatWizard
·
2026-02-20T22:42:00Z (7 months ago)
The key fact here is that regular languages are exactly the languages which can be decided by a computer with constant memory. This is basically the definition of a finite state automaton. From here it is easy to see these facts. You've already basically observed this for union, but complementation and intersection are not difficult. * Intersection: A computer can recognize a regular language with constant memory, and it can negate its output with constant memory. * Union: If two languages can be recognized with constant memory we can run both those programs (in parallel or serially) and take the logical and of the results. This takes at most constant+constant=constant memory.