chomsky hierachy

 Chomsky Hierachy(1959)

The great scientist Chomsky, it gives a hierarchy of grammar audible into the type that is type 3 grammar, type 2 grammar type 1, grammar, and Type 0 grammar. type 3 grammar is the most restricted grammar while Type 0 is unrestricted grammar.

TYPE -0 

Type 0 grammar is also called face structure grammar or unrestricted grammar. The language used in this type of grammar is type 0 language. Turing machine is based on Type 0 language. it is represented as Alpha(α) tends to beta(β).

                                                    α   →  β

where alpha contains any combination of terminals and nonterminals, there should be at least one nonterminal at LHS or alpha side, whereas beta can be terminal or nonterminal.

TYPE - 1

Type 1 grammar is also called context-sensitive grammar. The language used in this type of grammar is type 1 language. linear bounded automata are based on type -1. 

for example:

                            α   →  β

                              | α |≤|β|     and there should be no null set on the right-hand side.

All Type 1 Grammars are Type 0 but vice versa are not true.

TYPE - 2

type 2 grammar is also called context-free grammar. the language used is contest-free language.

push down automata or PDAs are based on this type of grammar.

for example:

                             α   →  β

                                  | α|=1

TYPE -3

Type 3 grammar is also called regular grammar and the language used in this is type 3 language.

finite automata are based on Type 3 grammar.

for example: 

                          α   →  β

                                  | α|=1, where β Is a single Terminal followed by a single nonterminal.

 Grammar tuples

Grammar of any language or in terms of formal language we having four tuples that describe any grammar. four tuples that grammar are known non- terminals(N), terminals(T), production(P) and start symbol(S). Grammar tuples can be represented as 

                                              (G)={N,T,P,S}

Non- terminal(N): Non terminals adulterated by the capital letters and these cannot be further expanded like {A,B,C....}

  Terminals(T):  Terminals are limited by the lower case alphabets And these and these can be further expanded like {a,b,c...}

Productional(P): These are the rules that is used to generate any terminals in the grammar.

Start symbol(S): It is in starting of an grammar from the non terminal and goes to terminal at the end.

automation theory

Automation theory/Computation theory

automation theory or it is called also called computational theory it is a type of a model that deals with the theory which is an abstract thing and give some input but the user and get some output it also checks whether the input is suitable for the machine to compute or not if it is computable then it executes yes if not then its an me computer is also a type of machine which also works on the same principal by giving some input by the hardware from the user side and after processing it will gives an output.

Theory of computation deals with the program that were expressed in the form of algorithm these algorithm are the recipe for carrying out some input to output transformation It tells us about how to compute a function most functions have no algorithm to compute but still can be automated and computed

competition deals with 3 major properties language automata and grammar that is LAG.

L stands for language

A stands for finite automata or automata

G stands for grammar.

LANGUAGE

language or formal language is a starting or beginning of any learning like English language it is characterised into 2 parts finite and infinite language. Before learning any language let's  begin with the symbol of any language

Symbol : single always characterised with the lower alphabet like 0,2,4,a,b,%,+ etc

Alphabet: alphabets are always denoted by Sigma end within curly braces symbols are separated by commas like  sigma ( Σ) ={ 0,1}

                                ={a,b,5}

                                ={a,b,0,3,%,+}

Word/String:  strings are the finite set of symbols selected from particular alphabet for example

                               (Σ) ={0,1}           string =         0110,1000,101001.......

Language: language is a collection of all those strings or words chosen from a particular alphabet electric always represented by a capital letter. Language further classified into 2 parts infinite and finite languages

finite language: in finite length we having the length of the strings that is that can be countable for example 

                  string having length 2 with alphabet 2 and 4:

                  L ={22,24,44,42}

infinite language: this type of language have infinite number of length of strings that is uncountable for example:   

                   string having length at least one a

                 L = {a,aa,aaa,aaaaa,...........}

Length of string: length of string is defined as the length of the language of each alphabet separated by commas for example:  L = {01,01,0111}

                                      modulus of each alphabet as x1,x2,x3

                                         |x1|=2

                                         |x2|=2

                                          |x3|=4

Power of sigma:   set of all strings of length zero is equal to sigma 0 =2^0

                              set of all strings of length one is equal to sigma 1=2^1

Kleen closure () = set  of all strings off all length possible on a set {a, b}

Automata/finite automata: automata or finite automata is a type of machine or model to check whether a string is a part of a language or not if it is yes then it will gives the no.

Finite automata depends only on the state then automata is without memory and if it depends on the state and input as well then it will depends on the memory automata or finite automata is divided into 2 parts first is with output and without output.