Theory Of Computation

Concept:- General_idea: click_me L={a^n b^n c^n | n>=1} w={abc,aabbcc,aaabbbccc,....} a a a b b b c c c  X a a Y b b Z c c X X a Y Y b Z Z c Step_1: Replace a by X and go right side. TM tape can move any side. It has infinite memory in both side. And it can remember previous states details. Step_2: Replace b by Y and go right side of tape. Step_3: Replace c by Z and turn left till X .  Step_4: After seeing X(capital X) replace next a by X and do same loop. Step_5: X portions finished. Step_6: Move to Y states. Denote it for one move first and after that notate self loops. Goto final state Z in self loop. Finally stop turing machine. Success. Next step: How to add self loop states? Ok listen me... For that we are taking two steps X a a Y b b Z c c X X a Y Y b Z Z c  Just understand in between symbols. And make it as self loops. If any doubt please post comments..I can explain it. Small editing...This one...

Full Explanation: For General_idea: Visit my blog. You need to type password "mescecse". Click_me For the Question_expln : Click_here

pf : No need to consider any trees on fewer than 3 vertices (WHY?). If the radius of the tree on n ≥ 3 vertices is one, then there is a vertex with eccentricity 1, which means it is connected to all other points. Claim: this center is unique. Assume otherwise, then another point is connected to all other points as well, including the known center. Taking an edge from this point to the known center, another edge out to a third distinct point, and finally an edge back to this point gives a cycle. That contradicts that this graph is a tree. Now let T be a tree with radius r > 1. Remove all vertices of degree 1 and their associated edges. This creates a graph of radius r − 1, which we can assume by induction has either 1 or 2 centers, which would obviously be the centers T. Reference: [1] 9.1 Introduction to Trees ,Available: click_me 

Arun Anoop M  BTech PG Diploma MTech MPhil (PhD) ASSISTANT PROFESSOR, Department of Computer Science & Engineering MES College Of Engineering,Kuttipuram Kerala, INDIA  E-mail:             arunanoopm@gmail.com     Phone: +91 9497394076 Whatsapp_number:  +91 9497394076 =================================================== Arun Anoop M  BTech PG Diploma MTech MPhil (PhD) PhD Research Scholar(January 2016 Batch). Under Anna University,Chennai Research Center: VCET,Madurai. Guide: Dr.S.Poonkuntran,             Professor,Dept. Of CSE,VCET,Madurai. If anyone want Online class please mail me or whatsapp me. First mail me your university syllabus. GATE Oriented class: 1. Datastructure 2. Theory of Computation 3. Functional dependancy in DBMS 4. Master's theorem in Algorithms

https://cs09506.wordpress.com/ password is mescecse

QUESTION is L=(AB)+  where A=11|10 and B=000|110 Download JFLAP from www. jflap .org/ jflap tmp/ Then Windows_Button+R ie; RUN Type cmd or command Then type java –jar <filename.jar> L=(AB)+      where A=11|10 and B=000|110 From this ….. Before design …what we need….Our question is L=(AB)+  where A=10|11 and B=110|000. W={10110,10000,11110,11000,1011010110,1000010000,……..} First I drawn the diagram based on first four inputs….Then I drawn an epsilon state to Initial state. How to write CFG(Grammar):- q0 as S,q1 as A and so on. S -> 1A A -> 1B | 1A B -> 1C | 0C C -> 1D | 0D           D -> 0E               E -> S | epsilon

Design View: By JFLAP Software Concept :  aaabbb Case1: XaaYbb Case2:XXaYYb Case3:XXXYYY Case 1: Read first 'a' and replace it by 'X' Then read first 'b' and replace it as 'Y' What i am doing is .....Meaning of a^n b^n is " Equal no: of a's must followed by equal no: of b's " In Case 1 : I read first 'a' and First 'b'. Before reading Second 'b'....Should read Second 'a' .... Then continue the steps.....Finally 'B' reads....Machine will stop... Transitions concept will continue ......

-Alan turing. -Language: Recursively Enumerable Language -Unrestricted Grammar (Why because there is no restriction for data reading .... Read data from Either Left or right side) - Input Tape:        ----------- B B  <string divided and keep in each cells> B B --------------- Finite Control Use "Tape head" to read  at a time one letter from input-tape cell. - Formal Definition M=(Q,Sigma,Toe,Delta,q0,B,F)                // 7 tuples or 7 elements...that we need to develop a TM Delta maps from Delta: Q X Toe -> Q X Toe X {L,R,S} Movements are L(Left),R(Right),S(Stationary)

Difference between DFA & NFA DFA  means Deterministic Finite Automata .  From one state to another only one input symbol is using. NFA  means Non- Deterministic Finite Automata.  There may be more than one transition from one state to another using same symbol.

        My Old Google site:  Click (" https://sites.google.com/site/cse09506mesce/home ")          1) Computation is the sequence of steps performed by the computer.         2) Computation is the process of execution of an algorithm that involves take some inputs and apply some operation then will get some output. Output may be accepted or rejected based on the input string. In My point of view eg:        In neural network we having inputs,operation and outputs....Operation may be called as activation function. Finite Automata           The word automata  comes from greek word automata that means "self acting". self acting->Something is doing something by itself.           we will see the term Automata.  Automata-> is the study of abstract computing devices or machin...

https://sites.google.com/site/cse09506mesce/home

Theory Of Computation is a "theoretical computer science". Is a branch of computer science that deals with whether and how efficiently problems can be solvable on a computer.

I am sure....this time i will try to write one book about "Theory Of Computation".

Context-sensitive grammar Context-sensitive grammars are more general than context-free grammars but still orderly enough to be parsed by a linear bounded automaton. Linear bounded automaton In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA ) is a restricted form of nondeterministic Turing machine .    

Students actually today i am going to present this..... Turing Model The idea of a universal computational device was first described by Alan Turing in 1937. He proposed that all computation could be performed by a special kind of a machine, now called a Turing machine . He based the model on the actions that people perform when involved in computation. He abstracted these actions into a model for a computational machine that has really changed the world. The Turing model is a better model for a general-purpose computer. This model adds an extra element to the specific computing machine: the program . A program is a set of instructions that tells the computer what to do with dat a.  Universal Turing Machine A universal Turing machine , a machine that can do any computation if the appropriate program is provided, was the first description of a modern computer. It can be proved that a very powerful computer and a universal Turing machine can compute the same thing. We ...