Question

1. All questions assume the alphabet Σ = { a , b }.

a) List the first 10 strings in canonical order of the language in question b above (even number of a's or odd number of b's, where the a's and b's can occur in any order).

b) List the first 10 strings in canonical order of the language in question c above (a^mbⁿ).

Answer 1

Note: only one (first one) question can be answered.

Solution:

Canonical Order - In canonical ordering of strings, the strings are grouped according to the length, all such groups are ordered in increasing length, and all such strings in the group are ordered in a lexicographic way based on the alphabets used.

= {a, b}

Part a) - Even number of a's or odd nnumber of b's - {, b, ab, ba, aab, aba, baa, bbb, aaaa, aaab}