Exercise 1 (Homework 1).
(theory of languages)
From informal to formal descriptions
Given an alphabet \Sigma, interesting languages L\subseteq \Sigma^* can be often written using the set notation as L=\{w\in \Sigma^* \mid P(w)\}, where P(w) is a predicate P defined on word w. For instance, the language L of all words over \{a,b\} that contain the subword ab can be denoted as
L=\{w\in \{a,b\}^* \mid \exists x,y\in \{a,b\}^*\ w=xaby\}.
Write the formal languages over \Sigma=\{a,b\} for the following informal descriptions of P(w):
- To the right of every subword ab in w there is some subword ba.
- Word w contains both the subword ab and the subword ba.
- Between every two b’s in w there is some a.
- Every occurrence of b in w is in an even position (the first symbol of a word is in position 1).
- Word w has some prefix with at least as many b’s as a’s.
- In every prefix of w, the number of b’s is at least the number of a’s.
- Word w has some even-length prefix with at least as many b’s as a’s.
- Every even-length prefix of w has at least as many b’s as a’s.
- Word w has a prefix and a suffix of the same nonzero length, equal to each other, and strictly less than the length of the word.
- Word w is a palindrome, that is, w reads the same forwards as backwards, e.g. madam or rotator in English.