A composable-reset DFA (CR-DFA) is a five-tuple, Theory of Computation

Assignment Help:

Question 2 (10 pt): In this question we look at an extension to DFAs. A composable-reset DFA (CR-DFA) is a five-tuple, (Q,S,d,q0,F) where:
– Q is the set of states,
– S is the alphabet,
– d:Q×(S?{?})?Qisthetransitionfunction, – q0 ? Q is the start state, and
– F ? Q is the set of accept states.
Every CR-DFA must satisfy one additional property:
When running a CR-DFA one can take a ?-transition if and only if the input has already been exhausted, and d cannot have any cycles that have a ?-transition.
A CR-DFA differs from a DFA by the addition of a new symbol denoted ? which can only be used by the transition function. This symbol is not part of the alphabet of the DFA.
The run function for a CR-DFA is defined as follows:
dˆ 0 : Q × S * × S * ? Q dˆ0(q,e,w1) = q
if d(q, ?) is undefined. dˆ0(q, e, w1) = dˆ0(q', w1, w1)
if d(q, ?) = q'
dˆ0(q, aw, w1) = dˆ0(q', w, w1)
if d(q, a) = q' dˆ : Q × S * ? Q
dˆ ( q , w ) = dˆ ( q , w , w ) 0
1
We can see that the run function, dˆ, is defined interms of an auxiliary function called dˆ0. The latter takes three arguments: i. the current state, the input word, and a second input word called w1. The second input word is called an accumulator, and it will be used to remember the original input to the run function, but when defining the auxiliary run function we leave this arbitrary.
The definition of the auxiliary run function follows the definition of the run function for DFAs, but in the case where the input word has been exhausted we check to see if the transition function allows the input to be reset to w1, and if it does, then we call dˆ0 on the next state given by d, and the input word is reset to w1. If when the input is exhausted and the transition function does not allow a ?-transition, then we proceed as usual.
Note that the definition of acceptance for a CR-DFA is the same as for DFAs.
We now define an interesting language. Suppose S = {a, b, c, d, ?, ?} is an alphabet. The symbol ? represents a binary operation, and the symbols a, b, c, d, and ? represent inputs to the binary operation ?. The language L is defined by the following:
i. a,b,c,d,? ? L
ii. Foranyei ?S,thewordw=e1?e2?e3?···?en ?L
iii. For any w ? L, any well-balanced parenthesization of w is a member of L
iv. There are no other words in L.
The following are some example words in L:
a
b
c
d
?
(a?b) (a?(b?c)) (a?(b?(c?d))) a?b?c (a?b)?c
So the words of L are all the possible associations of applications of the binary operation ?. Define a CR-DFA in the diagrammatic from used with DFAs that recognizes the language L as defined above. In addition, describe why CR-DFAs are bad in practice.

Related Discussions:- A composable-reset DFA (CR-DFA) is a five-tuple

Turing machine, prove following function is turing computable? f(m)={m-2,if...

prove following function is turing computable? f(m)={m-2,if m>2, {1,if

Grammer, write grammer to produce all mathematical expressions in c.

write grammer to produce all mathematical expressions in c.

Myhill-nerode theorem, This close relationship between the SL2 languages an...

This close relationship between the SL2 languages and the recognizable languages lets us use some of what we know about SL 2 to discover properties of the recognizable languages.

Kleene closure, One might assume that non-closure under concatenation would...

One might assume that non-closure under concatenation would imply non closure under both Kleene- and positive closure, since the concatenation of a language with itself is included

Strictly k-local automata, Strictly 2-local automata are based on lookup ta...

Strictly 2-local automata are based on lookup tables that are sets of 2-factors, the pairs of adjacent symbols which are permitted to occur in a word. To generalize, we extend the

Computer achitecture, what is a bus and draw a single bus structure

what is a bus and draw a single bus structure

Automata, how to prove he extended transition function is derived from part...

how to prove he extended transition function is derived from part 2 and 3

Discrete math, Find the Regular Grammar for the following Regular Expressio...

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd