Question

Using the properties of Regular languages, mention which properties (i.e. the closure under certain operations) that help in constructing the following finite automata:

1- The FA that recognizes all RNA sequences that contain the subsequence ATA and also contains the subsequence TGA
2- The FA that recognizes all the words that start with "an" but do not end with "ed"
3- The FA that recognizes all the strings that are a reverse of those in question 2.
4- The FA that recognizes all the strings that do not start with "ba" or do not end with "th"

Answer 1

Regular languages have closure properties such as closure under concatenation, intersection, complement, and reversal which can be used to construct finite automata for specific language requirements.

Step-by-step explanation:

The properties that help in constructing the given finite automata are closure under concatenation, closure under intersection, and closure under complement.

1. FA for RNA sequences: We can construct an FA that recognizes RNA sequences containing the subsequence ATA by first constructing an FA that recognizes the subsequence ATA and then taking the intersection of this FA with another FA that recognizes RNA sequences. Similarly, we can construct an FA for TGA subsequence and then take the intersection of the two FAs to obtain the desired FA.
2. FA for words starting with 'an' and not ending with 'ed': We can construct an FA that recognizes words starting with 'an' by using concatenation operation to combine an FA that recognizes 'an' with an FA that recognizes any other word. Then, we can complement this FA to obtain the FA that recognizes words not ending with 'ed'.
3. FA for reversed strings of question 2: We can construct an FA that recognizes reversed strings by reversing the transition arrows of the original FA constructed in question 2.
4. FA for strings not starting with 'ba' or not ending with 'th': We can construct an FA that recognizes strings not starting with 'ba' by complementing the FA that recognizes strings starting with 'ba'. Similarly, we can complement the FA that recognizes strings ending with 'th' to obtain the desired FA.