The operation Perm(w), applied to a string w, is all strings that can be constructed by permuting the symbols of w in any order. For example, if w = 101, then Perm(w) is all strings with two l's and one 0, i.e., Perm(w) = {101, 110, 011). If L is a regular language, then Perm(L) is the union of Perm(w) taken over all w in L. For example, if L is the language L(0*1*), then Perm(L) is all strings of 0's and 1's, i.e., L((0+1)*). If L is regular, Perm(L) is sometimes regular, sometimes context-free but not regular, and sometimes not even context-free. Consider each of the following regular expressions R below, and decide whether Perm(L(R)) is regular, context- free, or neither: 1. (01)* 2.0*+1* 3. (012)* 4. (01+2)* a) Perm(L(0*+1*)) is context-free but not regular. Ob) Perm(L((01+2)*)) is context-free but not regular. Oc) Perm(L((01+2)*)) is not context-free. d) Perm(L((01)*)) is regular.

The operation Perm(w), applied to a string w, is all strings that can be constructed by permuting the symbols of w in any order. For example, if w = 101, then Perm(w) is all strings with two l's and one 0, i.e., Perm(w) = {101, 110, 011). If L is a regular language, then Perm(L) is the union of Perm(w) taken over all w in L. For example, if L is the language L(01), then Perm(L) is all strings of 0's and 1's, i.e., L((0+1)). If L is regular, Perm(L) is sometimes regular, sometimes context-free but not regular, and sometimes not even context-free. Consider each of the following regular expressions R below, and decide whether Perm(L(R)) is regular, context- free, or neither: 1. (01) 2.0+1 3. (012)* 4. (01+2)* a) Perm(L(0+1)) is context-free but not regular. Ob) Perm(L((01+2))) is context-free but not regular. Oc) Perm(L((01+2))) is not context-free. d) Perm(L((01)*)) is regular.

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

mplement a Java program that applies the Newton-Raphson's method xn+1 = xn – f(xn) / f '(xn) to search the roots for this polynomial function ax6 – bx5 + cx4 – dx3+ ex2 – fx + g = 0. Fill out a, b, c, d, e, f, and g using the first 7 digits of your ID, respectively. For example, if ID is 4759284, the polynomial function would be 4x6 – 7x5 + 5x4 – 9x3+ 2x2 – 8x + 4 = 0. The program terminates when the difference between the new solution and the previous one is smaller than 0.00001 within 2000 iterations. Otherwise, it shows Not Found as the final solution.
In this task, you will implement a recursive function all_perm(n: int) -> set[tuple[int, ...]] that takes an integer n> 0 and returns a set containing all the permutations of 1,2,3,..., n. Each per- mutation must be represented as a tuple. For example: • all_perm(1) • all_perm(2) • all_perm(3) {(1,)} {(1,2), (2,1)} == {(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)} %3D%3D Restrictions: Do not write a helper function. Your function must be recursive, and must work with sets and tuples directly. You are not allowed to import anything. Hints: Consider how we can use all_perm(2) to create the answer for all_perm(3). Perhaps the following diagram will help (pay close attention to the color coding and numbers in boldface fonts): all_perm(2) == {(1,2), (2,1)} all_perm(3) == {(3,1,2), (1,3,2), (1,2,3), (3,2,1), (2,3, 1), (2,1,3)} all_perm(4) == {(4,3,1,2), (3,4, 1,2), (3, 1, 4, 2), (3, 1,2, 4), (4, 1,3,2), (1,4,3, 2), (1,3,4,2), (1,3,2,4), (4, 1,2,3), (1,4,2,3), (1,2,4,3), (1,2,3,4),…
Construct a Java RE that describes the set of strings that arelegal REs over the binary alphabet, but with no occurrence of parentheses within parentheses. For example, (0.*1)* or (1.*0)* is in this language, but (1(0 or 1)1)*is not.
Must be new solution and run on GNU Common Lisp! Using Lisp, write a program that solves the Missionaries and Cannibals problem that uses a DFS( depth first search). It should use (mac start end). Start is the current state (which can be (3 3 l) and End is the goal state (which can be (0 0 r). This should output the sequences of moves needed to reach the end state from the start state. This should print nil if there is no solution. For example, the call should be something like this! Call: (mac '(3 3 l) '(0 0 r)) Output: ((3 3 l) (2 2 r) (3 2 l) (3 0 r) (3 1 l) (1 1 r) (2 2 l) (0 2 r) (0 3 l) (0 1 r) (1 1 l) (0 0 r))
Edsgar Dijkstra is known for his work on programming languages. Hecame up with a neat problem that he called the Dutch National Flagproblem: given a list of strings, each of which is either 'red', 'green', or 'blue'(each is repeated several times in the list), rearrange the list so that thestrings are in the order of the Dutch national flag—all the 'red' stringsfirst, then all the 'green' strings, then all the 'blue' strings.Write a function called dutch_flag that takes a list and solves this problem.
Implement a function that takes two strings of equal length and returns the distance between two strings is the number of positions at which the corresponding symbols are different.Check if thr given strings are of equal length, if not,return-1 PHYTHON LANGUAGE
Artificial Intelligence (Part - 1) ==================== The Towers of Hanoi is a famous problem for studying recursion in computer 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. (1) Propose a state representation for the problem?
Regular expressions are built recursively out of smaller regular expressions, using some rules described below. Each regular expression ?denotes a language ?(?), which is also defined recursively from the languages denoted by ?′? subexpressions. Given an alphabet ∑ = {0, 1}, write the language denoted by the following regular expressions:(i) 1(ii) 0 | 1(iii) (0 | 1)(iv) (0 | 1)∗(v) 1(0 | 1)∗(vi) 0 |1 (0| 1)
∑ = {C,A,G,T}, L = { w : w = CAjGnTmC, m = j + n }. For example, CAGTTC ∈ L; CTAGTC ∉ L because the symbols are not in the order specified by the characteristic function; CAGTT ∉ L because it does not end with C; and CAGGTTC ∉ L because the number of T's do not equal the number of A's plus the number of G's. Prove that L ∉ RLs using the RL pumping theorem.