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

L={a"b"a" | n,m=1,2,3....} is given. ni m n Draw the derivation tree for the string aaaabbbaaaa.
Evaluate the following FOL-wff using the given interpretation: (Vz)(Q(x) (By)(P(r,y) (Vx)P(y, r))) 1. U= {a, b} IT y P(r,y) y Q(y) a a. a a. b. a
Regular expression is an algebraic notation for describing sets of strings.A regular expression defines a language of strings over an alphabet. Regular expression is used to describe tokens of a programming language. Predict any five algebraic laws of regular expression and give their descriptions where appropriate.
Write a program in C language to evaluate and save the results of n subjects using array of structures. Assume that each student takes seven subjects of 100 marks each.
Find a most general unifier (if one exists) of the following pairs. P(y,a,b,y) and P(c,f,g,f) where a and b are constants, and f,g,y are variables. P(f(x),r(x),c) and P(w,r(q),q), where c is a constant, and x, w, q are variables.
Program in C
I. Given a pointer to a singly linked linear list write an algorithm which will take every node that has in the information field a negative number and put it at the front of the list and deletes every node that has a value between 250 and 500 in its information field. You have one external pointer to the front of the list (don't forget trailing pointers).
Write a progprogram in python language that take a string from user and print that and then take a integer and from that position remove the element from the string
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.
Given the following CFG S → OB A → 1AA|A B → OAA The following strings can be generated except i. 001 ii. 000 iii.0011 iv. 01 O A. i and iii O B. i and ii O C. iv only O D. ii only
Q2: Design a PDA for accepting a language {0^1m0n | m, n>=1} give the ID form as we explain in the lecture. Apply the string "00011000" on this PDA using ID transitions.
DDATA STRUCTURES AND ALGORITHMS WITH JAVA