Finite Automata

Question

What's is the meaning of the statement:-

 

An automatic is a cognitive device and a grammar is a generative device.

 

What does the word cognitive and generative mean in this respect.

Answer 1

Grammar is a generating device means "it defines the rules/productions for generating valid strings which collectively form a language."

Analogy-In English grammar statements follow rules as- Subject Verb Object. eg- She eats the apple.

Automata is cognitive device means "it reads the language generated by Grammar using its transitions"

Analogy- You are automata as- eg- "She eats the apple." You will read this and accept it. However, If I say "She eat the apple" , this is wrong as per English grammar and you will not accept this.

Comments

Thanks a lot for your simple and enriching answer:)

---

@Mamta , I have one confusion.. For a language there can be many grammars..So , a machine will accept only those strings which can be generated by that particular grammar...means we should have grammar to get the language...Now suppose , we have a unrestricted grammar and now according to you, TM reads the string based on that particular unrestricted grammar..but there is no membership algo for it to test whether this string can be generated by this grammar or not...So how machine will make the recursively enumerable language using that unrestricted grammar rules ?  Please explain..

---

"For a language there can be many grammars..So , a machine will accept only those strings which can be generated by that particular grammar...means we should have grammar to get the language"

True, that for a language there can be more than one grammar, and the corresponding machine will be the same for all those grammars(NOT which can be generated by that particular grammar).And yes we should have grammar "G" to get the language, L(G).

"Now suppose , we have a unrestricted grammar and now according to you, TM reads the string based on that particular unrestricted grammar."

Yes, TM reads the language generated by Unrestricted Grammar.

"but there is no membership algo for it to test whether this string can be generated by this grammar or not...So how machine will make the recursively enumerable language using that unrestricted grammar rules ?"

There is a membership algorithm for a given string which will always answer YES & accept, a given string if it can be generated by an unrestricted grammar G,  BUT there is no algorithm which answers NO& reject, a given string when it cannot be generated by an unrestricted grammar G. That's why Recursively Enumerable languages are called Turing Recognizable Languages reason as mentioned above - Turing Machines can only recognize the strings that are member of R.E language.

---

@Mamta ,got it..thank you for the explanation...