/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Q50P Question:聽Read the informal def... [FREE SOLUTION] | 91影视

91影视

Log out

Learning Materials

Features

Discover

Chapter 1: Q50P (page 90)

Question:Read the informal definition of the finite state transducer given in Exercise 1.24. Prove that no FST can output WR for every input if the input and output alphabets are {0,1}

Short Answer

Expert verified

Answer:

There is no finite state transducer can output WRfor every input if the input and output alphabets are {0,1} is proved.

Step by step solution

01

Step 1: Finite state transducer.

A finite state transducer (FST) is a type of deterministic finite automaton whose output is a string and not just accept or reject. Each transition of an FST (finite state transducer) is labeled with two symbols, one designating the input symbol for that transition and the other designating the output symbol.

02

No FST is possible for the given language.a).

Assume to the contrary that some finite state automaton or finite state transducer T, WRoutputs on input W. Consider the input strings . On input 00, T must output 00, and on input 01, T must output 10. In both cases, the first input bit is a 0 but the first output bits differ.

As given in the questionfinite state transducer (FST) is a type of deterministic finite automaton whose output is a string and not just accepts or reject. Each transition of an FST (finite state transducer) is labeled with two symbols, one designating the input symbol for that transition and the other designating the output symbol.

Operating in this way is impossible for an finite state automaton orfinite state transducer no finite state transduceris possible for the given languagebecause it produces its first output bit before it reads its second input. And here no such finite state automaton orfinite state transducercan exist.

Hence, there is no finite state transducer can outputWR for every input if the input and output alphabets are {0,1} is proved.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91影视!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

A homomorphism is a function f:危-鈫�螕*from one alphabet to strings over another alphabet. We can extend f to operate on strings by defining:f(w)=f(w1)f(w2)路路路f(wn),wherew=w1w2路路路wnandeachwi鈭�危.

We further extend fto operate on languages by defining f(A)={f(w)|w鈭�A},for any language A.

a. Show, by giving a formal construction, that the class of regular languages is closed under homomorphism. In other words, given a DFA Mthat recognizes Band a homomorphism f, construct a finite automaton role="math" localid="1660800566802" M0that recognizes f(B).Consider the machine role="math" localid="1660800575641" M0that you constructed. Is it a DFA in every case?

b. Show, by giving an example, that the class of non-regular languages is not closed under homomorphism.

If A is any language, let A13-13be the set of all strings in A with their middle thirds removed so that

A13-13={xz|forsomey,|x|=|y|=|z|andxyz鈭�A}.

Show that if A is regular, then A13-13is not necessarily regular

Question: The following are the state diagrams of two DFAs , M1 and M2 . Answer the following questions about each of these machines.

a. What is the start state ?

b. What is the set of accept states ?

c. What sequence of states does the machine go through on input aabb ?

d. Does the machine accept the string aabb ?

e. Does the machine accept the string 蔚 ?

Give regular expressions generating the languages of Exercise 1.6.

a. {begins with a 1 and ends with a 0}

b. { w|wcontains at least three 1s}

c. { w|wcontains the substring 0101 (i.e., w = x0101y for some x and y)}

d. { w|whas length at least 3 and its third symbol is a 0}

e. { w|wstarts with 0 and has odd length, or starts with 1 and has even length}

f. { w|wdoesn鈥檛 contain the substring 110}

g. { w|the length of wis at most 5}

h. { w|wis any string except 11 and 111}

i. { w|every odd position of w is a 1 }

j. { contains at least two 0s and at most one 1}

k. {蔚,0}

l. { w|wcontains an even number of 0 s, or contains exactly two 1s}

m. The empty set

n. All strings except the empty string

Question: Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection, and complement.

a.{0n1m0n|m,n猢�0}b.{0m1n|m鈮�n}c.{w|w鈭�{0,1}*isnotapalindrome}d.{wtw|w,t鈭�{0,1}+

See all solutions

Recommended explanations on Computer Science Textbooks

Problem Solving Techniques

Read Explanation

Issues in Computer Science

Read Explanation

Cloud Services

Read Explanation

Fintech

Read Explanation

Functional Programming

Read Explanation

Data Representation in Computer Science

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.