This chapter covers regulated language models, which are extended by additional mathematical mechanisms that prescribe the use of rules during the generation of their languages. An important advantage of these models lies in controlling their language-defining process and, therefore, operating in a more deterministic way than general models, which perform their derivations in a completely unregulated way. More significantly, the regulated versions of language models are stronger than their unregulated versions. The chapter covers grammars regulated by states, grammars regulated by control languages, matrix grammars, programmed grammars, and regulated automata.

Chapter Contents:

• 12.1 Grammars regulated by states
• 12.1.1 Definitions and examples
• 12.1.2 Generative power
• 12.2 Grammars regulated by control languages
• 12.2.1 Definitions and examples
• 12.2.2 Generative power
• 12.3 Matrix grammars
• 12.3.1 Definitions and examples
• 12.3.2 Generative power
• 12.3.3 Even matrix grammars
• 12.3.3.1 Definitions and examples
• 12.3.3.2 Generative power
• 12.3.3.3 Summary
• 12.4 Programmed grammars
• 12.4.1 Definitions and examples
• 12.4.2 Generative power
• 12.5 Regulated automata and computation
• 12.5.1 Self-regulating automata
• 12.5.2 Self-regulating finite automata
• 12.5.2.1 Definitions and examples
• 12.5.2.2 Accepting power
• 12.5.2.3 n-Turn first-move self-regulating finite automata
• 12.5.2.4 Language families accepted by n-first-SFAs and n-all-SFAs
• 12.5.3 Self-regulating pushdown automata
• 12.5.3.1 Definitions
• 12.5.3.2 Accepting power
• 12.5.4 Open problems
• 12.5.5 Regulated acceptance with control languages
• 12.5.6 Finite automata regulated by control languages
• 12.5.6.1 Definitions
• 12.5.6.2 Conversions
• 12.5.6.3 Regular-controlled finite automata
• 12.5.6.4 Context-free-controlled finite automata
• 12.5.6.5 Program-controlled finite automata
• 12.5.7 Pushdown automata regulated by control languages
• 12.5.7.1 Definitions
• 12.5.7.2 Regular-controlled pushdown automata
• 12.5.7.3 Linear-controlled pushdown automata
• 12.5.7.4 One-turn linear-controlled pushdown automata
• 12.5.8 Self-reproducing pushdown transducers
• 12.5.9 Definitions
• 12.5.10 Results

Inspec keywords: formal languages; automata theory; grammars

Other keywords: control language regulated grammars; mathematical mechanisms; language generation; state-regulated grammars; language-defining process; regulated language models; regulated automata; matrix grammars; programmed grammars

Subjects: Automata theory; Formal languages and computational linguistics