Non Determinism of Finite Automata
Journal Title: International Journal for Research in Applied Science and Engineering Technology (IJRASET) - Year 2014, Vol 2, Issue 9
Abstract
The basic finite automata model has been extended over the years with different acceptancemodes (nondeterminism, alternation), new or improved devices (two-way heads, Pebbles, nested pebbles) and with cooperation. None of these additions permits recognitionof non-regular languages. The purpose of this work is to investigate a new kindof automata which is inspired by an extension of 2DPDAs. Mogensen enhanced thesewith what he called a WORM (write once, read many) track and showed that Cook’s Linear-time simulation result still holds. Here we trade the pushdown store for nondeterminismor a pebble and show that the languages of these new types of finite automataare still regular. The conjunction of alternation or of nondeterminism and a pebblepermits the recognition of non-regular languages. We have given examples of languages thatare easy to recognize and of operations that are easy to perform using these WORM tracks under nondeterminism. While somewhat similar to Henie machines, our modelsdo not require an explicit time bound on their computations.
Authors and Affiliations
Akshit Chauhan, Deepak Kumar, Deepak Chandel
Analysis and Simulation of E-Shape Microstrip Patch Antenna for Wideband Applications
This paper presents the design and simulation of E-shape microstrip patch antenna with wideband operating frequency for wireless application. The shape will provide the broad bandwidth which is required in various appli...
Spatial Variability of Groundwater Chemical Quality for Drinking and Irrigation Purposes in Parts of Nagaon and Morigaon Districts, Assam, Using Geoinformatics
The spatial variability in the chemical quality of groundwater resources in parts of Nagaon and Morigaon Districts, Assam was studied by considering pre-monsoon and post-monsoon groundwater samples. Quality analysis was...
Compressive strength of fly ash based Geopolymer concrete
The present paper is an effort to investigate the compressive strength properties offly ash based geopolymer concrete. Large scale production of cement is causing environmental problems. This has made the researchers to...
Experimental Study on Light Transmitting Conctrete (LiTraCon)
Now days, a Small buildings are replaced by high rise buildings and sky scrapers. This arises one of the problem in deriving natural light in building, due to obstruction of nearby structures. Due to this problem use of...
Back Pressure Algorithm in Communication Networks Using Shadow Queuing
Back-pressure-based adaptative routing algorithms area unit wherever every packet is routed on a presumably totally different path. Algorithms usually lead to poor delay performance and involve high implementation compl...