Hoofdstuk 11: A hierarchy of formal
languages and automata
Inhoud:
• Relation between Turing machines and languages
• Is every language determined by some Turing machine?
• Hierarchy of languages and grammars
1 Recursive(ly enumerable) languages
Bij beslisbare taal → stopt in niet finale state indien woord niet geaccepteerd wordt
Semi-beslisbaar → loopt voor eeuwig indien woord niet geaccepteerd wordt.
2 Enumerating languages
• Can you enumerate all elements of recursive language?
• What about a recursively enumerable language?
2.1 Are all languages recursively enumerable?
Stelling:
For any non-empty alphabet, there exists a language that is not recursively enumerable.
Bewijs:
In hoofdstuk 10 aangetoond dat er eindig aantal TM zijn over een gegeven alfabet. Er zijn echter
oneindig veel talen over een gegeven niet leeg alfabet. Verder accepteert een TM maar 1 taal
waardoor er dus voor elk niet leeg alfabet minstens een taal zal bestaan die we niet met een TM
kunnen accepteren.
• This means that there exist languages for which we cannot even write a program that
accepts them.
• This means that there are computational problems we cannot solve with a computer (more
on that next chapter)
1
languages and automata
Inhoud:
• Relation between Turing machines and languages
• Is every language determined by some Turing machine?
• Hierarchy of languages and grammars
1 Recursive(ly enumerable) languages
Bij beslisbare taal → stopt in niet finale state indien woord niet geaccepteerd wordt
Semi-beslisbaar → loopt voor eeuwig indien woord niet geaccepteerd wordt.
2 Enumerating languages
• Can you enumerate all elements of recursive language?
• What about a recursively enumerable language?
2.1 Are all languages recursively enumerable?
Stelling:
For any non-empty alphabet, there exists a language that is not recursively enumerable.
Bewijs:
In hoofdstuk 10 aangetoond dat er eindig aantal TM zijn over een gegeven alfabet. Er zijn echter
oneindig veel talen over een gegeven niet leeg alfabet. Verder accepteert een TM maar 1 taal
waardoor er dus voor elk niet leeg alfabet minstens een taal zal bestaan die we niet met een TM
kunnen accepteren.
• This means that there exist languages for which we cannot even write a program that
accepts them.
• This means that there are computational problems we cannot solve with a computer (more
on that next chapter)
1
