We consider the alphabet = {a, b}. We want to design a finite automaton that recognises...

Transcribed Image Text:

We consider the alphabet = {a, b}. We want to design a finite automaton that recognises the language Lof the strings that do NOT contain the substring "bb". We start with the following non-deterministic automaton N that recognises the complement of language L, that is, the set of strings that DO contain the substring "bb": a, b a, b b b 2 1. Use the determinisation procedure to transform this automaton N into a deterministic finite automaton D that recognises the same language. 2. Transform D into an automaton that recognises the language L. [4 marks] [3 marks] 3. Show that, if you were to apply the same transformation as in step 2 to the non-deterministic automaton N, the language of the obtained automaton would not be L. [3 marks] We consider the alphabet = {a, b}. We want to design a finite automaton that recognises the language Lof the strings that do NOT contain the substring "bb". We start with the following non-deterministic automaton N that recognises the complement of language L, that is, the set of strings that DO contain the substring "bb": a, b a, b b b 2 1. Use the determinisation procedure to transform this automaton N into a deterministic finite automaton D that recognises the same language. 2. Transform D into an automaton that recognises the language L. [4 marks] [3 marks] 3. Show that, if you were to apply the same transformation as in step 2 to the non-deterministic automaton N, the language of the obtained automaton would not be L. [3 marks]

Answer rating: 100% (QA)

To answer your questions lets go through each step Determinisation of N into D To determinize the gi... View the full answer