Design deterministic finite state transducers

Assignment Help Theory of Computation

Reference no: EM13704478

Design deterministic finite state transducers that implement the subsequent context sensitive rules:

Part 1: a FST that changes a in its input to b if it is preceded by cc: cca -> ccb

Part 2: a FST that encloses ab in parentheses if it is followed by c: abc -> (ab)c

Suppose that the input alphabet is {a,b,c}. So the output alphabet in part a is the same as the input, while the output in part b is {a,b,c,(,)}.

The FSTs will be infinite loops, where the set of accept states is not well-defined, but for consistency you can suppose that once the respective rule was applied, the FST enters an accept state.

For part (b) you can also assume that the input will not end in ab.

You have to satisfy the requirements specific in the instruction. I am having difficulty with this problem because I do not know where to start.

Reference no: EM13704478

Questions Cloud

Program to read the numbers and add certain digit : Write a program that will read in 5 numbers and add 10 to the first number, 20 to the second number, and 30 to the third number, 40 to the fourth and 50 to the 50th.

Calculate the final grade : write must ask the user to input the percent score for each of these items then calculate the final grade.

Implement the solution for tracking the number of subscribe : In a social media news feed, users are required to subscribe to the news feed before receiving any news or updates. Users can only subscribe to each news feed only once up to five different feeds.

What settings are used to make that decision : What allows the IP layer to determine where to send a packet next and what settings are used to make that decision?

Design deterministic finite state transducers : Design deterministic finite state transducers that implement the subsequent context sensitive rules:

How can you acquire the digital evidence from the computer : How can you acquire the digital evidence from the computer and which methods of collection would you use and why - would you use any special tools, programs, or methods?

Calculate c with various sets of values for a and b : Even if we were to declare variables a and b as integers, why might we still need to declare c as a ?double?

Will the direction and magnitude be integers or doubles : Define a Physics_vector class which consists of a struct containing the direction and magnitude, and also define a function

Subnetting and supernetting : What are the key differences between the following two terms: subnetting and supernetting? Provide examples for each - Do you expect IPv6 will replace IPv4 completely in the coming future

User Account

All Pages