UNIT 4
Turing machines
Given Σ, then the Kleene Star Closure of the alphabet Σ, denoted by Σ*, is the collection of all strings defined over Σ, including Λ.
Plus Operation is same as Kleene Star Closure except that it does not generate Λ (null string), automatically.
Given Σ, then the Kleene Star Closure of the alphabet Σ, denoted by Σ*, is the collection of all strings defined over Σ, including Λ.
Plus Operation is same as Kleene Star Closure except that it does not generate Λ (null string), automatically.
You can use other symbol for alphabet but we are mostly use sigma symbol.
2. Define Regular Expression?
Regular Expression is the generalized form of any regular language through which you can construct any string related to that language.
Take an example from your handouts
L1 = {Λ, a, aa, aaa, …} and L2 = {a, aa, aaa, aaaa, …} can simply be expressed by a* and a+, respectively.
so a* and a+ are the generalized form of Languages L1, L2.
And a* and a+ are called the regular expressions (RE) for L1 and L2 respectively.
3. What Is The Concept Of Fa Also Known As Fsm ( Finite State Machine) ?
FA (Finite Automaton) is a finite state machine that recognizes a regular language. In computer science, a finite-state machine (FSM) or finite-state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. The internal states of the machine carry no further structure. This kind of model is very widely used in the study of computation and languages.
4. What Is The Difference Between Fa , Tg , Gtg. ?
In every FA, we mark transitions with single letter of the given alphabet but in TG transitions can be marked with letters or strings (combination of letters).
In every FA, every state shows transition for all letters of given alphabet but in any TG it is not necessary to show all transition for all letters of given alphabet. In TG, we may or may not show all letter transitions according to requirement. We can also show transitions on reading any strings in TGs but it is not possible in FA’s. In GTG Directed edges connecting some pair of states are labeled with regular expressions . It may be noted that in GTG, the labels of transition edges are corresponding regular expressions. In TG we write strings and in GTG we are bound to write RE. Every FA is also a TG but not every TG is FA.
5. What Is The Difference Between Fa’s And Tg’s .why We Need Tg’s When We Have Fa’s?
The Transition Graphs (TG) differ from FA in the following areas
We have been given more freedom in TG’s. But this freedom is on the cost of more memory and processing power it means that if we implement TG’s on computer using some programming language it will need more memory and processing power of computer than used in the implementation of FA’s.
6. What Is The Concept Of The Union Of Fa’s ?
When we take Union of two FA’s it means that resultant FA’s should accept all the words that were accepted by the two FA’s individually. It is like taking union of two sets, the resultant set contain members of both sets.
For example
Let A ={1,3,5,7,9}
and
B = {0,2,4,6,8,10}
then, A U B = { 0,1,2,3,4,5,6,7,8,9,10 }
you can see that A U B contain elements of both sets similar is the case with FA’s.
7. What Is The Difference Between Is Tg And Gtg ?
In TG, there are letter transitions for the strings. While in GTG, one can write whole RE as a transition from one state to another one.
8. What Is Difference Between Fa’s And Nfa’s. Are They Opposite To Each Other ?
FA stands for finite automata while NFA stands for non-deterministic finite automata, In FA there must be a transition for each letter of the alphabet from each state. So in FA number of transitions must be equal to (number of states * number of letter in alphabet).
While in NFA there may be more than one transition for a letter from a state. And finally every FA is an NFA while every NFA may be an FA or not.
9. Define Instantaneous description(ID) in PDA.
ID describe the configuration of a PDA at a given instant.ID is a triple such as (q, w ,γ ) , where q is a state , w is a string of input symbols and γ is a string of stack
symbols. If M =( Q, Σ ,Ґ ,δ ,q0 ,Z0 ,F ) is a PDA we say that
(q,aw,Zα) |-----( p, w, βα) if δ(q,a,Z) contains (p, β ).
M
‘a’ may be Є or an input symbol.
Example: (q1, BG) is in δ(q1, 0 , G) tells that (q1, 011, GGR )|---- ( q1, 11,BGGR).
10. Specify the two types of moves in PDA.
The move dependent on the input symbol(a) scanned is:
δ(q,a,Z) = { ( p1, γ1 ), ( p2,γ2 ),……..( pm,γm ) }
where q qnd p are states , a is in Σ ,Z is a stack symbol and γi is in Ґ*. PDA is in state q , with input symbol a and Z the top symbol on state enter state pi Replace symbol Z by string γi.
The move independent on input symbol is (Є-move):
δ(q,Є,Z)= { ( p1,γ1 ), ( p2,γ2 ),…………( pm,γm ) }.
Is that PDA is in state q , independent of input symbol being scanned and with
Z the top symbol on the stack enter a state pi and replace Z by γi.
