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
Keywords
Related Articles
- EP ID EP18628
- DOI -
- Views 249
- Downloads 12
Study of Accidents on Yamuna Expressway�s section joining Noida and Greater Noida
Road being key component of infrastructure play vital role in development of any area. It is general observation that road accidents also increase simultaneously with road development. A study is carried out to find the...
Design of EBG Superstrate to Improve the Performance of Patch Antenna
The frequency selective surface (FSS) properties of a planar EBG unit cell due to meander variations are studied. The meander EBG unit cell has meander line inductors and inter digitated capacitors to provide FSS charac...
Applying Altman’s Business Failure Prediction Model To Indian NSE Small Cap And Mid Cap Auto And Auto Ancillary Companies
It has long been established that a detailed ratios analysis has good potential to determine and establish the financial performance of an organization by evaluating its operational and financial efficiencies. Altman’s...
Multi-Response Optimization of Process Parameters Based On MRSN for D2 Steel Using WEDM Process with Plain Brass Wire and Zinc Coated Brass Wire
Wire Electrical Discharge Machining plays an important role in precision machining. The material removal rate, higher the best and surface finish, lower the best, are mostly required as output response. But it is a well...
An Advanced Latent Fingerprint Matching by Using Level Three Features
Latent fingerprint identification is of critical importance in forensic applications. Fingerprint features are generally described at three different levels, namely, Level 1 (ridge flow), Level 2 (minutiae points) and L...