SKEDSOFT

Automata | Comp. Sc. Engg.

Introduction: A regular set (language) is a set accepted by a finite automaton.

Closure: A set is closed under an operation if, whenever the operation is applied to members of the set, the result is also a member of the set. For example, the set of integers is closed under addition, because x y is an integer whenever x and y are integers. However, integers are not closed under division: if x and y are integers, x/y may or may not be an integer.

There are several operations defined on languages:

L1 L2 È : strings in either L1 or L2.

L1 L2 Ç : strings in both L1 and L2.

L1L2 : strings com posed of one string from L, fol lowed by one string from L2.

–L2 : All strings (over the same alpha bet) not in L1.

L1* : Zero or more strings from L1 con catenated together

L1 L2 - : strings in L1 that are not in L2.

LR1 : strings in L1, reversed.

We shall show that the set of regular languages is closed under each of these operations.

Union, Concatenation, Negation, Kleene Star, Reverse

The general approach is as follows:

  1. Build automata (DFA or NFA) for each of the languages involved.
  2. Show how to combine the automata in order to form a new automaton which recognizes the desired language.
  3. Since the language is represented by NFA/DFA, we shall conclude that the language is regular.

Union of L1 and L2

  1. Create a new start state
  2. Make a l-transition from the new start state to each of the original start states.

Concatenation of L1 and L2

  1. Put a l-transition from each final state of L1 to the initial state of L2.
  2. Make the original final states of L1 non-final.

Intersection and Set Difference

Just as with the other operations, it can be proved that regular languages are closed under intersection and set difference by starting with automata for the initial languages, and constructing a new automaton that represents the operation applied to the initial languages. In this construction, a completely new machine is formed, whose states are labelled with an ordered pair of state names: the first element of each pair is a state from L1 and the second element of each pair is a state from L2.

  • Begin by creating a start state whose label is (start state of L1, start state of L2).
  • Repeat the following until no new arcs can be added:
  1. Find a state (A, B) that lacks a transition for some x in S.
  2. Add a transition on x from state (A, B) to state (d (A, x), d (B, x)). (If this state does not already exist, create it).

Negation of L1

  • Start with a complete DFA, not with an NFA
  • Make every final state nonfinal and every nonfinal state final.

Kleene star of L1

  • Make a new start state; connect it to the original start state with a l-transition.
  • Make a new final state; connect the original final state (which becomes nonfinal) to it with l-transitions.
  • Connect the new start state and new final state with a pair of l-transitions.

Reverse of L1

  1. Start with an automaton with just one final state.
  2. Make the initial state final and final state initial.
  3. Reverse the direction of every arc.

The same construction is used for both intersection and set difference. The distinction is in how the final states are selected.

Intersection: Make a state (A, B) as final if both

  1. A is a final state in L1 and
  2. B is a final state in L2

Set Difference

Mark a state (A, B) as final if A is a final state in L1, but B is not a final state in L2.