7. The following shows the state transition diagram of a Turing machine for language A = {a² In>0}.For example, strings a, aa, aaaa, and aaaaaaaa are members of language A. Modify this Turing machine torecognize language B = {a(2)-1 | n ≥ 0). For example, strings e, a, aaa, and aaaaaaa are members oflanguage B. You can modify, add, or remove transitions, but you cannot add or remove any states.a → a, L0-0,41+1, L0-1,LU-1,Lz→z,R00-1,LU-1,La➡z, R31-0, R1-0, R2Daa,Raa, R10-0, R1-1,RU-U,Rreject0-0, R31+1,RU-URaccept

Answered: Image /qna-images/answer/78d4c702-394b-451f-bfdb-07a85d434057.jpg

7. The following shows the state transition diagram of a Turing machine for language A={a²|n20). For example, strings a, aa, aaaa, and aaaaaaaa are members of language A. Modify this Turing machine to recognize language B= (a)-1|n20). For example, strings e, a, aaa, and aaaaaaa are members of language B. You can modify, add, or remove transitions, but you cannot add or remove any states. 31-0, R aa, L 0-0,4 1+1,4 0-1,4 U-1,4 zz, R 0 0-1,4 U-1,4 1-0, R 2 aa, R 1 DataR 0-0, R 1-1,R U-UR reject 0-0,R 51-1,R U-UR accept

7. The following shows the state transition diagram of a Turing machine for language A={a²|n20). For example, strings a, aa, aaaa, and aaaaaaaa are members of language A. Modify this Turing machine to recognize language B= (a)-1|n20). For example, strings e, a, aaa, and aaaaaaa are members of language B. You can modify, add, or remove transitions, but you cannot add or remove any states. 31-0, R aa, L 0-0,4 1+1,4 0-1,4 U-1,4 zz, R 0 0-1,4 U-1,4 1-0, R 2 aa, R 1 DataR 0-0, R 1-1,R U-UR reject 0-0,R 51-1,R U-UR accept

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

This problem considers strings that can be made from the alphabetA= {‘a’, ‘b’, ‘c’}.a. Write a recursive definition for the set of strings that have at least one 'a' character.b. Write a recursive definition for the set of strings that do not start with the letter 'a'.
Given L = {w = {a, b}*: |w| is even}, the correct statements are: (aa U ab Uba U bb)* is a regular expression that generates L. (ab Uba)* is a regular expression that generates L. aa U ab U ba U bb is a regular expression that generates L. ab U ba is a regular expression that generates L.
Artificial Intelligence (Part - 2) ==================== The Towers of Hanoi is a famous problem for studying recursion incomputer science and searching in artificial intelligence. We start with N discs of varying sizes on a peg (stacked in order according to size), and two empty pegs. We are allowed to move a disc from one peg to another, but we are never allowed to move a larger disc on top of a smaller disc. The goal is to move all the discs to the rightmost peg (see figure). To solve the problem by using search methods, we need first formulate the problem. Supposing there are K pegs and N disk. (2) What is the size of the state space?
The 4th problem mimics the situation where eagles flying in the sky can be spotted and counted.FindEagles: a recursive function that examines and counts the number of objects (eagles) in aphotograph. The data is in a two-dimensional grid of cells, each of which may be empty (value 0) orfilled (value 1 to 9). Maximum grid size is 50 x 50. The filled cells that are connected form an object(eagle). Two cells are connected if they are vertically, horizontally, or diagonally adjacent. Thefollowing figure shows 3 x 4 grids with 3 eagles. 0 0 1 21 0 0 01 0 3 1 FindEagle function takes as parameters the 2-D array and the x-y coordinates of a cell that is a part ofan eagle (non-zero value) and erases (change to 0) the image of an eagle. The function FindEagleshould return an integer value that counts how many cells has been counted as part of an eagle and havebeen erased. The following sample data has two pictures, the first one is 3 x 4, and the second one is 5 x 5 grids. Notethat your program…
Here is a description of a Turing machine. The input alphabet is (a, b). The state set is: {90, 91, 92, 93, 94, 9acc, grej} The transition function is given in the table below: 9⁰ (9₁, a, R) b (92, b, R) (grej, *, R) 93 94 (qacc. a, R) (qrej, a, R) (arej, b, R) (qacc, b, R) (arej,*, R) (qrej, *, R) (a) Draw the configuration of the Turing machine after 3 steps on input "aabba". When the Turing machine is in the initial configuration, it has executed zero steps. a 91 (9₁, a, R) * 92 (92, a, R) (9₁, b, R) (93, *, L) (92, b, R) (94*, L) (b) For how many steps does the Turing machine run on input string "a" before the Turing machine halts? Does the Turing machine accept the string "a"? (c) Simulate the Turing machine on input "aaba". Does it accept? Draw the final two configurations of the Turing machine computation. In the last configuration, the Turing machine is either in the accept or reject state. (d) Simulate the Turing machine on input "aabb". Does it accept? Draw the final two…
= {a'ba' | i > 0}. Let E = {a, b}. Let L = Give a Turing machine (TM) that accepts the language L. Assume ; that, when the TM starts, the head is on a blank symbol, A, and the input string is immediately after that blank symbol on the tape. For example, if the input string were aaabaaa, then the inital tape configuration would be A a a aba a a
IN HASKELL PROGRAMMING LANGUAGE PLEASE In case you do not know it: the game is played on a 3x3 grid that is initially empty. Two players are playing, by alternatingly making moves. A move by a player places their token (an X for player 1, an O for player 2) into a cell that was empty. We are using algebraic notations for indexing the positions in the board, with A,B,C indexing the columns and 1,2,3 the rows. Specifically, these coordinates would be used in the implementation for moves made by a human player. If the X X O Figure 1: Sample board position same token appears 3 times in any of the three columns, three rows or two main diagonals the game is over and that player wins. If the grid is filled without that happening the game is a draw. For the depicted board, we have Xs in positions C3 and A2, and an O in position B1. It would be O’s turn to make a move; a legal move would be C2, but it is not a good move, because X can force a win by responding A1. O cannot force a win, but…
Finite language is a language with finite number of strings in it, i.e., there exist exactly k strings in this language such that k eNand k #00. For a finite language L, let |L| denote the number of elements of L. For example, |{A, a, ababb}| = 3. (Do not mix up with the length |x| of a string x.) The statement |L,L2| = |L1||L2| says that the number of strings in the concatenation LL2 is the same as the product of the two numbers |L1| and |L2|. Is this always true? If so, prove, and if not, find two finite languages L1, L2 S {a, b}* such that |L1L2| # |Li||L2l.
Write a program that performs the following functionalities:1. Fibonacci: a recursive function that computes the fibonacci series, which is defined as followsfibonacci (n) = fibonacci(n-2) + fibonacci(n-1)fibonacci(0) = 0fibonacci(1) = 1 So the fibonacci looks like: 0 1 1 2 3 5 8 13 21 34 …. Therefore, fibonacci(4) = 3, fibonacci(5) = 5, fibonacci(7)=13 2. Sum: a recursive function that computes the sum of integers 1, 2, 3, …., n for a given number n. So Sum(6) should return 1 + 2 + 3 + 4 + 5 + 6 , i.e. 21.sum(n) = n + sum(n-1) 3. Largest: a recursive function that computes the largest value for an integer array of positiveand negative values. For example, for the array below, the function largest should return 22,which is the largest value in the array. You can assume there are no more 20 integers in thearray. Think of how to formulate the recurrence relation in this problem yourself. 4. The 4th problem mimics the situation where eagles flying in the sky can be spotted and…
A uwuified sentence is sentence that has been transformed using a made-up Internet language in which some of the letters in the words are replaced by something else. The exact scheme is described below: Any uppercase/lowercase R or L is replaced by w/w, respectively. • If we encounter an o/o in a word, check if the previous letter (if it exists) is an M/m or N/n. If the previous letter is one of these, insert the lowercase letter y in between them, regardless of the capitalization of the other letters. • All other characters are left unchanged. Some examples: Professor will be converted to Pwofessow (There are two r's that are replaced by w's. Since the two o's aren't proceeded by an M/n or N/n, no y will be inserted.) LLunoacyo will be converted to wwunyoacyo (The two L's will be replaced with two ws according to the first rule. Then the first o will have a y inserted in front of it between then and the o according to the second rule. The last o won't have a y inserted in between…
Problem 4 We can use lists of numbers like l to represent a mathematical vector. Recall from math classes that a vector is an object with a magnitude and direction. The magnitude is the sqrt of the sum of the squares (for a vector (x,y) it's the Pythagorean theorem for the magnitude (x^2 + y^2)**(1/2)). For a vector of any other length, the formula generalizes to (l[0]^2 + l[1]^2 + l[2]^2 + ... )**(1/2). For this problem use l from Problem 1 and a for loop to compute the magnitude of l with the result stored in l_mag. For l above, its magnitude is 12.96. Python gives you the ** exponentiation operator to raise a number to a power. You could also import math and use math.sqrt(). l = [1, 2, 3, 4, 5, 7, 8] Please give proper explanation and typed answer only.
In this work, we ask you to design a deterministic Finite Automaton (FA) to recognise arithmetic expressions. When we say arithmetic expression, we mean a kind of expression you can type in a very basic desk calculator. That is, neither variables nor brackets are allowed. It contains only numbers and four arithmetic operators, +, -, *, and /. The following are some examples of arithmetic expression: 1. Any number string with or without signs - e.g. 3, -1, +10, 3.14, -0.70 and 099. 2. Number strings mixed with arithmetic operators e.g. 3+5, -1+2*3, 7/10-0.7, and -1.4-+8.2. An example of FA diagram for recognising a non- negative integer is given below. You may use it as a start point. You need to add a few more states and transitions to handle numbers with decimal point and signs (e.g. -5, +2, 0.21, -32.6, +99.05, but not the form 1.0E-3). Most importantly, you also need to add a few more things to deal with the arithmetic operators +, -, *, /. →start 0-9 digit 0-9