March 20, 2021
1.1. Grammars
Let G be a grammar, than G= (V, T, P, S)
Where, V= Set of Non-terminals.
T= Set of terminals.
P= Set of Production rules or productions.
S= Start Symbol.
1.1.1. There are four types of grammar:
· Regular Grammar(RG)
· Context Free Grammar(CFG)
· Context Sensitive Grammar(CSG)
· Recursive Enumerable Grammar(REG)
1.2. Formal Languages
Formal language is a set of all strings where each string is restricted over a particular form. We can say that it is a set of all strings permitted by the rules of formation.
Types of Languages
· Regular Language(REG): A language generated by regular grammar and accepted by finite automata is called Regular Language.
· Deterministic Context Free Language(DCFL): A language accepted by a deterministic push down automata is called DCFL.
· Context Free Language(CFL):A language generated by context free grammar and accepted by a non-deterministic push down automata is called a “CFL”.
· Context Sensitive Language(CSL):A language generated by context sensitive grammar and accepted by a linear bound automata is called “CSL”.
· Recursive Language (REC): A language accepted by the Halting Turing machine is called recursive language.
or
If a Language can be enumerated in a lexicographic order (Particular order) by some Turing machine then such a language is called recursive or REG.
· Recursive Enumerable Language (REL): A language accepted by Turing machine is called recursive enumerable language or REL.
1.3. Automaton or Automata
· Automata acts as a recognizer or acceptor. It is a machine that accepts or recognizes the strings of a language (L) over an input alphabet ∑.
Ex.
Input String (w) Automaton Yes (w is valid string )
over ∑. accept L over ∑ No (w is invalid string)
· Automaton act as generator or enumerator or transducer. It is an machine that can produce the output over any alphabet for the given alphabet ∑.
Ex.
Automaton
Input String (w) Produces o/p output string w’
over ∑.