The Automata (Self - Acting ) Theory is the study of abstract machines use to computing problems .
An Alphabet is a finite set of symbols .
Language
An Language on a alphabet Σ is a subset of Σ*
An Automaton is described by an Language which it accepts .
Grammar
A Grammar of a Language is a set of rules just what that language follows .
A language must have a grammar to describe and generate it . A Grammar G can be told as the grammar of Language L iff G generates only L .
If G is a Grammar and L is Language generated by it and A is the automaton accepting only that language then we can write this as →
L = L(G) A = A(L)
Or ,
L ↔ G ↔ A
Normally we have input string in an array/tape . Our machine read them one by one . There is a pointer initially pointed at q0 and shift according δ to from states to state of Q. The given string is accepted if the pointer reside in an accepting state at the end of the string .
We have many zones of Languages and corresponding Automata and Grammar
Formal definition
- Automaton
- An Automaton is represented formally by (Q,Σ,δ,q0,F) →
- 1. Q is a finite set of states.
- 2. Σ is a finite set of symbols, called the alphabet of the automaton.
- 3. δ is the transition function, that is, δ: Q × Σ → Q.
- 4. q0 is the start state, that is, the state of the automaton before any input has been
processed, where q0 ∈ Q. - 5. F is a set of states of Q (i.e. F⊆Q) called accept states.
An Alphabet is a finite set of symbols .
Language
An Language on a alphabet Σ is a subset of Σ*
An Automaton is described by an Language which it accepts .
Grammar
A Grammar of a Language is a set of rules just what that language follows .
A language must have a grammar to describe and generate it . A Grammar G can be told as the grammar of Language L iff G generates only L .
If G is a Grammar and L is Language generated by it and A is the automaton accepting only that language then we can write this as →
L = L(G) A = A(L)
Or ,
L ↔ G ↔ A
Normally we have input string in an array/tape . Our machine read them one by one . There is a pointer initially pointed at q0 and shift according δ to from states to state of Q. The given string is accepted if the pointer reside in an accepting state at the end of the string .
We have many zones of Languages and corresponding Automata and Grammar
| Language
|
Grammar | Automata |
| Regular | Regular | Finite Automata |
| Context Free (CFL) | Context Free | PDA |
| Context Sensitive (CSL) | Context Sensitive | LBA |
| Decidable / Recursive | TM accepts and rejects | |
| Recursively Enumerable | TM can only accept | |
| Undecidable |
Only regular language can be parsed by finite state machines . CFL can be parsed using FSM and a stack . CSL can be parsed by LBA . The most powerful machine is TM i.e a infinite array and a FSM [Finite state machine ] .
No comments:
Post a Comment