Regular Expressions

Regular Expressions
Regular expressions can be used to define languages. A regular expression is like a "pattern"; strings that match the pattern are in the language, strings that do not match the pattern are not in the language.
The construction of regular expressions is defined recursively, starting with primitive regular expressions, which can be composed using typical operators to form more complex regular expressions.
Definition of Regular Expressions :
Let ? be a given alphabet.
• ?, ?, a, for a ? ? are (primitive) regular expressions.

If r, r1, r2 are regular expressions, then
• r* star closure
• r1 + r2 union
• r1 • r2 concatenation
are regular expressions.
Note: ? = ?


Equivalence of FA and RE
For every regular expression there is an equivalence NFA with ? - moves
a* = zero or more of a’s
a+ = one or more of a’s
the expression r may be ?, ?, or a for some a in ?, the NFA with ?-moves are :




r = ? r = ? r =a

r = r1+r2










r = r1r2




r= r1*










Pushdown Automata

A pushdown automata (PDA) recognize CFL it is essentially like NDFA but have an extra component called stack. This extra component allows the automaton to have memory(in principle, infinite amount of memory), and to recognize some no regular languages.
A PDA can write (push) a symbol on the top of stack or remove (pop) a symbol from the top the stack. The stack is unlimited and works as LIFO storage device.


A “move” of a PDA will depend on :
1-Current state of machine
2- Current symbol in input tape
3- Current symbol on the top of stack

With each “move”, the machine can
-Move into a new state
-Push symbol to the stack, remove or no any thing.
The stack
- The stack has its own alphabet ( ? )
- Included in this alphabet is a special symbol used to indicate an empty stack (Z0)
- This special symbol should not be removed from the stack
To formalize:
A pushdown automata (PDA) is a 7-tuple:
M = (Q, ?, ?, q0, z0, A, ?) where :
Q = finite set of states
? = tape alphabet
? = stack alphabet
q0IQ = start state
Z0I ? = initial stack symbol
A ? Q = set of accepting states
Transition function
• The transition function ??:
During a move of a PDA:
• At most one character is read from the input tape
L transitions are okay (don’t move the reading head)
• The topmost character is popped from the stack
Unless it is Z0
• The machine will move to a new state based on:
- The character read from the tape
- The character on the top of stack
- The current state of the machine
• Zero or more symbols from the stack alphabet are pushed onto the stack.


Transition function continued:
??: Q x (??E?{?}) x ????????????? (finite subsets of Q x ?* )

Domain:
• Q = state
• ? E {L} = current symbol read from the tape
• ? = current symbol on the top of stack

Range
• Q = new state
• ?* = symbols pushed on the stack

When the character L is read from the TAPE, it means that we are out of input letters. The L-edge will lead to ACCEPT if the state we have stopped in is a final state and to REJECT if the Processive stops in a state that is not a final state.

Example
? (q,a,a)=(p,aa)
. Meaning:
- when in state q,
- reading in an ‘a’ from the tape
- with an ‘a’ on the top of stack
. The machine will
- go into state p
- push an ‘a’ on the top of stack

Configuration of a PDA
(p, x, ?) where :
• p is the current state
• x is a string indicating what remains to be read on the tape
• ? is the current contents of the stack.




The language accepted by a PDA:
There are two natural ways to define this language:
1- Define the language accepted to be the set of all inputs for which some of sequence of moves cause the PDA to empty stack. This language called “language accepted by empty stack”
2- Define the language accepted to be the set of all inputs for which some choice of moves causes the PDA to enter a final state.