What is an alphabet, in general? What characteristics must it have?
An alphabet is a nonempty, finite set
What is the definition of a language? That is, what is a language in general (as opposed to the definition of a particular language).
A language is a set of strings over a given alphabet.
Draw a diagram of a finite state machine that accepts (answers yes on) all strings of a's and b's that have at least two a's and exactly one b, and rejects all other strings.
Answer:
Give a regular expression that describes the set of strings from the preceding problem.
Any string in this language has exactly one b. It has either 0, or 1 or more than one a to the left of that b. There can always be extra a's to the right of the b, but there must be at least 2 a's. So an expression that describes this language is
aaa*ba* + abaa* + baaa*
where + indicates union. (I don't have a union key.)
Give one member and one nonmember of the language described by regular expression a*b(a+b)*, where + is the union operator and the alphabet is {a,b}.
Suppose that the following NFA is converted to a DFA by the subset construction. Draw a diagram of the resulting DFA. Label each state by the set to which it corresponds.
Answer:
