Complexity of Binary and Uniary Operations on Regular Grammar
Rajesh Kumar1, Manju2
1Assistant Prof. Rajesh Kumar, Computer Science & Applications, CRM Jat College, Hisar, Haryana, India.
2Assistant Prof. Manju, Computer Science & Applications, CRM Jat College, Hisar, Haryana, India.
Manuscript received on June 21, 2017. | Revised Manuscript received on June 26, 2017. | Manuscript published on July 05, 2017. | PP: 42-45 | Volume-7 Issue-3, July 2017. | Retrieval Number: C3031077317/2017©BEIESP
Open Access | Ethics and Policies | Cite
©The Authors. Published By: Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: It appears that the state complexity of each operation has its own special features. Thus, it is important and practical to calculate good estimates for some commonly used general cases. In this paper, the author consider the state complexity of combined Boolean operations on regular language and give an exact bound for all of them in the case when the alphabet is not fixed. Moreover, the author show that for any fixed alphabet, this bound can be reached in infinite cases.
Keywords: Alternating finite automaton, Automata, Combined operations, Estimation, Formal languages, Multiple operations, State complexity.