Search notes:

Grammar (parsing)

A grammar is a set of rules that describe a language. The rules consist of
The set of strings that can be generated by a grammar is a language.
A notation for a syntax free grammar is EBNF.
Lexical symbols:
Lexical symbols are composed of characters (note the distinction).

Types of grammars (Chomsky hierarchy)

Grammar accepted Language accepted Automaton / Machine
Type 0 Unrestricted grammar Recursively enumerable language Touring machine (Deterministic (DTM) vs Non-deterministic (NTM), the default being DTM
Type 1 Context sensitive grammar Context sensitive language Linear bounded automata (LBA) (also deterministic vs. non-deterministic)
Type 2 Context free grammar Context free lanuage Push down automata (PDA), also D vs N, the default being NPDA
Type 3 Regular grammar Regular language Finite automata (FA), also DFA vs NFA, the default being DFA

Expressive power

Type 0 grammars have the most expressive power, Type 3 the least expressive power.
The expressive power of of DFAs is equal to the expressive power of NFAs. Therefore, every NFA can be converted into a DFA.
The expressive power of NPDAs is greated than the expressive power of DPDAs. Therefore, some NPDAs can't be converted into a DPDA.
The expressive power of DTMs is equal to the expressive power of NTMs.

Memory requirements

FA: no memory needed
PDA: FA + 1 stack
TM = FA + 2 stacks

Misc

The Chomsky hierarchy is sometimes also referred to as Chomsky-Schützenberger hierarchy, after the French mathematician Marcel-Paul Schützenberger.

Index

Fatal error: Uncaught PDOException: SQLSTATE[HY000]: General error: 8 attempt to write a readonly database in /home/httpd/vhosts/renenyffenegger.ch/php/web-request-database.php:78 Stack trace: #0 /home/httpd/vhosts/renenyffenegger.ch/php/web-request-database.php(78): PDOStatement->execute(Array) #1 /home/httpd/vhosts/renenyffenegger.ch/php/web-request-database.php(30): insert_webrequest_('/notes/developm...', 1759406788, '216.73.216.42', 'Mozilla/5.0 App...', NULL) #2 /home/httpd/vhosts/renenyffenegger.ch/httpsdocs/notes/development/languages/parsing/grammar/index(96): insert_webrequest() #3 {main} thrown in /home/httpd/vhosts/renenyffenegger.ch/php/web-request-database.php on line 78