Construct diagram versions of finite automata that accept the following languages.
computer science
Description
Question 1
Construct diagram versions of finite automata that accept the following languages.
1. {anbm|n≥1,m≥1}{anbm|n≥1,m≥1}
2. {anbm|n is even OR m is odd}{anbm|n is even OR m is odd}
3. {w∈{0,1}∗|w=ε or w ends in 1}{w∈{0,1}∗|w=ε or w ends in 1}
4. {w∈{0,1}∗|w starts and ends with 0}{w∈{0,1}∗|w starts and ends with 0}
5. {w∈{0,1}∗|w starts and ends with the same letter}{w∈{0,1}∗|w starts and ends
with the same letter}
Question 2
For one of your diagrams in question 1, write down a full formal definition of the finite
automaton.
Question 3
In the Java programming language, any text written between the characters /∗/∗ and ∗/∗/ is
considered a comment, so the compiler will ignore it. Let’s suppose we use the
alphabet Σ={x,/,∗}Σ={x,/,∗} where xx stands for any normal English letter. A string is
considered a valid comment if it starts with /∗/∗, ends with ∗/∗/, and does not
have ∗/∗/ anywhere except at the end of the string. Write a diagram version of a finite automaton
that recognises the language of valid Java comments.
For clarity, the rules of this question follow the Java language. The start asterisk and end asterisk
must be separate. So /∗//∗/ is not accepted, even though we might argue that it starts and ends
with the correct symbols. This also means that /∗/∗//∗/∗/ should be accepted! These examples
are somewhat ambiguous in the English-description of this problem, and it is an excellent
argument for using models like finite automata to describe languages, because they cannot have
any ambiguity.
