Theory of computation basic term in hindi

Theory of computation basic in hindi

1. Automata क्या है ?
2. Finite automaton की formal definition:
3. Symbol क्या है?
4. Alphabet क्या है?
5. String क्या है?
6. Prefix क्या है?
7. Suffix क्या है?
8. Proper prefix/suffix क्या है?
9. Concatenation of a string को समझाइये?
10. Reverse of a string को समझाइये ?
11. Kleene Star क्या है?
12. Kleene Closure / Plus क्या है?
13. Language क्या है?

Term "Automata" को Greek word "αὐτόματα" से लिया गया है | जिसका मतलब "self acting" होता है|

automaton जोकि automata का plural है, वह abstract self-propelled computing device होता है | जो कि automatically operations के predetermined sequences को follow करता है|

ऐसा automaton जिसमें states की संख्या finite होती है, finite automaton या finite state machine कहलाता है|

Finite automaton की formal definition:

Automaton को 5-tuple से प्रदर्शित किया जा सकता है (Q, Σ, δ, q0, F)

Q : states का finite set होता है.

Σ symbols का finite, set होता है, जिसे automaton का alphabet कहा जाता है

δ : transition function होता है.

q0: initial state होता है जहां से input processed (q0 ∈ Q) किए जाते हैं

F: Q (F ⊆ Q) state / states का final state होता है |

संबंधित शब्दावली:

Symbol:

Symbol TOC में basic building block होते हैं|

 उदाहरण:
 a,b,0,1, pictures

Alphabet :

Symbols का finite set होता है या यह symbols का combination होता है| यह non-empty set होता है | इसे Σ से व्यक्त किया जाता है

 उदाहरण:
 Σ ={0,1} binary के लिए
 Σ ={0,1,2,3,4,5,6,7,8,9} 
 decimal numbers के लिए
 Σ = {a, b, c, d....z} 
 lowercase में character strings के लिए
 Σ = {A,B,C,D......Z} 
 lowercase में character strings के लिए
 alphabet का set है 
 जहाँ ‘a’, ‘b’, ‘c’, और ‘d’ symbols है |

String :

Σ से प्राप्त किए गए symbols का finite sequence होता है|

alphabet set Σ = {a, b, c, d} पर 
‘cadcab’ एक valid string है |

String की length :

यह string में स्थित symbols की संख्या होती है | जिसे |S| से denote किया जाता है|

 यदि S=‘cadcab’, तब |S|= 6
 या
 यदि |S|= 0, यह empty string कहलाता है
 जिसे λ या ε से व्यक्त किया जाता है |

Prefix:

prefix को हम front end of string भी कहते हैं।

दिए गए स्ट्रिंग के कितनी भी संख्या में 
leading sybmol/symbols से क्रमशः
 बनाए गए अन्य string। .
उदाहरण:
String :
w=0111
w=ababb
Prefix:
^,0,01,011,0111
^,a,ab,aba, abab, ababb
 

Suffix:

Suffix को rear या end of string
कहा जाता है|
दिए गए स्ट्रिंग के कितने भी संख्या में 
trailing symbols/symbol से बनाए
गए अन्य स्ट्रिंग
उदाहरण:
String:
w=ababb
^,b,bb,abb, babb,ababb
^(null string)को empty string 
भी कहा जाता है।
 

Proper prefix/suffix:

किसी string का ऐसा prefix/suffix जिसमे string खुद शामिल न हो।क्योंकि किसी string का suffix/prefix निकालते समय हम वो string भी prefix/suffix मानते है जिस string का suffix/prefix निकाल रहे होते है।

Concatenation of a string :

w=a₁ a₂.........a_m

V=b₁ b₂..........B_n

wv =a₁ a₂.........a_n b₁ b₂....... b_m

Reverse of a string:

Reverse string हमे तब प्राप्त होती है जब हम सिंबल्स को रिवर्स ऑर्डर में लिखते हैं

w=a₁ a₂ .....a_m

w^R=a _m a _m-1.... a ₂ a ₁

Kleene Star :

Kleene Star , Σ* , symbols या strings के सेट पर unary operator होता है | Σ*, जो सभी संभव strings का Σ जिसमे λ भी शामिल है पर सभी संभव length का infinite set देता है |

 वर्णन :
 Σ * = Σ0 U Σ1 U Σ2 U…….
 जहां Σp p length के सभी संभव
 strings का सेट होता है |
 उदाहरण:
 यदि Σ = {a, b}, 
 Σ *= {λ, a, b, aa, ab, ba, bb,………..}
 

Kleene Closure / Plus:

Set Σ +, जो सभी संभव strings का Σ पर जिसमे λ शामिल नही है पर संभव सभी length पर infinite set देता है |

वर्णन
Σ + = Σ1 U Σ2 U Σ3 U…….
उदाहरण : 
यदि Σ = { a, b } , 
Σ+ 
={ a, b, aa, ab, ba, bb,…}

Language :

कुछ alphabets Σ के लिए एक language Σ* का subset होता है| यह finite या infinite हो सकता है|

 उदाहरण:
 यदि language , 2 length के 
 सभी संभव strings 
 Σ = {a, b} पर लेता है 
 तब L = { ab, bb, ba, bb}

>

^	null string होती है।
|^|=0	null string की length 0 होती है।
^w = w^ = w = ∈ Σ	कोई null string जो किसी string w को concatenate कर रही है वह उस string के बराबर होगी जिसमे string w null string को concatenate कर रहा है । और इन दोनों के बराबर वह string w होगा जो alphabet Σ से belong करता है।
|a|=1 ∀ w ∈ ∑	Length 1 होगी ।
|wa| = |w| +1 ∀ w ∈ ∑	किसी string में किसी एक symbol का Concatenation की length उस string की length और 1 होती है जो कि सभी string w के लिए जो ∑ में है
aR=a	किसी सिंगल symbol के string का Reverse वही string होता है |