Example of Regular Expression

Ex. 6:
Find a regular expression corresponding to the language of all strings over the alphabet { a, b } that contain no more than one occurence of the string aa.

Solution:
If there is one substring aa in a string of the language, then that aa can be followed by any number of b. If an a comes after that aa, then that a must be preceded by b because otherwise there are two occurences of aa. Hence any string that follows aa is represented by ( b + ba )*. On the other hand if an a precedes the aa, then it must be followed by b. Hence a string preceding the aa can be represented by ( b + ab )*. Hence if a string of the language contains aa then it corresponds to the regular expression ( b + ab )*aa( b + ba )* .

If there is no aa but at least one a exists in a string of the language, then applying the same argument as for aa to a, ( b + ab )*a( b + ba )* is obtained as a regular expression corresponding to such strings.

If there may not be any a in a string of the language, then applying the same argument as for aa to , ( b + ab )*( b + ba )* is obtained as a regular expression corresponding to such strings.
Altogether ( b + ab )*( + a + aa )( b + ba )* is a regular expression for the language.

Regular Language-formal definition

As I said in my previous post, we will discuss formal definitions of a single term at a time. Today, we are going to discuss “Regular languages”

Regular languages over an alphabet (Formal Definition):
The collection of regular languages over an alphabet Σ is defined recursively as follows:
 the empty language Ø is a regular language.
 the empty string language { ε } is a regular language.
 For each a ∈ Σ, the singleton language { a } is a regular language.
 If A and B are regular languages, then A ∪ B (union), A B (concatenation), and A* (Kleene star) are regular languages

NLIN SPACE AND LIN SPACE

As I said in this post I am going to continue context sensitive languages and grammars.
Computationally the context-sensitive languages are equivalent with linear bounded non-deterministic Turing machine. That is a non-deterministic Turing machine with a tape of only kn cells, where n is the size of the input and k is a constant associated with the machine.
This means that every formal language that can be decided by such a machine is a context-sensitive language, and every context-sensitive language can be decided by such a machine.
This set of languages is also known as NLIN-SPACE, because they can be accepted using linear space on a non-deterministic Turing machine.
The class LIN-SPACE is defined the same, except using a deterministic Turing machine. Clearly LIN-SPACE is a subset of NLIN-SPACE, but it is not known whether LIN-SPACE=NLIN-SPACE. It is widely suspected they are not equal.

Automata Step by Step

Now we also need definition of “regular grammar”

Regular Grammars:

Regular grammars describe exactly all regular languages and are in that sense equivalent to finite state automata and regular expressions. Moreover, the right regular grammars by themselves are also equivalent to the regular languages, as are the left regular grammars.

Every regular grammar is a context-free grammar. Every context-free grammar can be easily rewritten into a form in which only a combination of left regular and right regular rules is used. Therefore, such grammars can express all context-free languages. Regular grammars, which use either left-regular or right-regular rules but not both, can only express a smaller set of languages, called the regular languages. In that sense they are equivalent with finite state automata and regular expressions.

What is a regular language? It is important to understand “regular language” for better understanding of above definitions. We will discuss it in our next post..