Additionally, a relevant example is expounded.Ī rapid development in formal languages has made a profound influence on computer science, especially played a greater role in the design of programming languages, compiling theory and computational complexity since formal language system was established by Chomsky in 1956. And the construction algorithm 5 of the equivalent conversion from finite automata to left linear grammar is presented as well as its correctness proof. The simplified forms of the algorithms and their proofs are given. Some complicated conversion algorithms have also been in existence. The equivalence exists between regular grammar and finite automata in accepting languages. Keywords: Regular Grammar Finite Automata NFA DFA After this production rule we have following final diagram of finite automata accepting L (G).1Department of Information Technology, Yingtan Vocational and Technical College, Yingtan, China 2School of Information Technology, Jiangxi University of Finance and Economics, Nanchang, China.Įmail: November 21 st, 2012 revised December 20 th, 2012 accepted December 31 st, 2012 Similarly, for the production rule A 2 -> 0includes a transition from q2 to qf with label 0. After this production rule we have following partial diagram of finite automata. The production rule A 1 -> 0A 2 includes a transition from q1 to q2 with label 0. The production rule A 0 -> 1A 2 includes a transition from q0 to q2 with label 1. After this production rule, we have following partial diagram of finite automata. The production rule A 0 -> 0A 1 includes a transition from q0 to q1 with label 0. Initially we have 4 states of finite automata M. The states q0, q1, q2 corresponds to A 0, A 1, A 2, and qf is the new final state of M. Let M = (Q, ?, q 0, F, ?) be a finite-automata that accepts L (G), where P is the set of production rules defined as:Ĭonstruct a finite-automata that accepts the language generated by a given grammar G. Let G = (V, T, P, S) be a regular grammar, where In this N has transition from q k to q f with label b.įrom the construction, it is clear that A0 => b1A1 => b1b2A2 => b1b2b3A3 => ….=>b1bn-1 => b1….bn, if and only if there is a path in N starting from initial state q0 and ends on final state qf with path value b1b2….bn. In this N has transition from q i to q j with label b. Let G = (V, T, P, S) be a right linear grammar.
So, first of all we will construct a NFA equivalent to given right linear grammar which accepts the language defined by the given regular grammar G. The regular languages are recognized by finite automata.
If G is a regular grammar then L (G) is a regular language. The relationship of regular grammar and finite automata is shown below: Finite Automata consists of 5 tuples (Q, ?, q 0, F, ?).
The term finite in finite automata is that it has a limited number of states and the limited number of alphabets in the strings. Finite Automataįinite Automata are the simplest model accepted the language called regular language. A and B belongs to variables and a is a terminal. Left Linear Grammar: A left linear grammar is a grammar G = (V, T, P, S) such that all the production rules P are one of the following forms: The left-hand side of production rule in right linear grammar consists of only one symbol from set of variables, and right hand side contains either strings of terminals or only one variable present at rightmost position. A and B belongs to variable V and a is a terminal. Right Linear Grammar: A right linear grammar is a grammar G = (V, T, P, S) such that all the production rules P are one of the following forms: Following are the types of Linear Grammar: Linear Grammar: Agrammar is called linear in which at most one non-terminal can occur on the right side of any production rule. Equivalence of Regular Grammar and Finite AutomataĪ regular grammar or type-3 defines the language called regular language that is accepted by finite Automata.A Regular Grammar G consists of 4 tuples (V, T, P, S).
0 kommentar(er)
