The followng 4-tuple regualr grammar is given: G=({S,A,B}, {a,b}, S, {S→AB, A⇒aA|a, B→bB|b}) Assume that L is the regular language generated by this grammar. Which string(s) will not belong to L? aaaabb abbbbbb aaaabbbba ababababab

The followng 4-tuple regualr grammar is given: G=({S,A,B}, {a,b}, S, {S→AB, A⇒aA|a, B→bB|b}) Assume that L is the regular language generated by this grammar. Which string(s) will not belong to L? aaaabb abbbbbb aaaabbbba ababababab

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

Suppose a string Z is formed by interspersing the characters from other two strings X and Y. The new string Z is called a shuffle of X and Y if characters in Z com- ing from the same string still keep the order as in the original string. For example, the strings PRODGYRNAMAMMIINCG and DYPRONGARMAMMICING are both shuffles of DYNAMIC and PROGRAMMING: PRODGYRNAMAMMIINCG DYPRONGARMAMMICING Given three strings A[1..m], B[1..n], and C[1..m+n], design a dynamic programming algorithm to determine if C is a shuffle of A and B.
1. Let L = {w {a, b}* : w contains bba as a substring that starts in an odd numbered position in the string (where numbering starts at 1)}. For example, bbbbaaaab L, while bbbaaaab L. Show an NDFSM that accepts L
Q8 Hive Minds: Migrating Birds You again control a single insect, but there are B birds flying along known paths. Specifically, at time t each bird b will be at position (x¿(t), Yb(t)). The tuple of bird positions repeats with period T. Birds might move up to 3 squares per time step. An example is shown below, but keep in mind that you should answer for a general instance of the problem, not simply the map and path shown below. Your insect can share squares with birds and it can even hitch a ride on them! On any time step that your insect shares a square with a bird, the insect may either move as normal or move directly to the bird's next location (either action has cost 1, even if the bird travels farther than one square).
Subsequent words def words_with_letters(words, letters): This problem is an excuse to introduce some general discrete math terminology that helps make many later problem speci0ications less convoluted and ambiguous. A substring of a string consists of characters taken in order from consecutive positions. Contrast this with the similar concept of subsequence of characters still taken in order, but not necessarily at consecutive positions. For example, each of the 0ive strings '', 'e', 'put', 'ompu' and 'computer' is both a substring and subsequence of the string 'computer', whereas 'cper' and 'out' are subsequences, but not substrings. Note how the empty string is always a substring of every possible string, including itself. Every string is always its own substring, although not a proper substring the same way how all other substrings are proper. Concepts of sublist and subsequence are de0ined for lists in an analogous manner. Since sets have no internal order on top of the element…
A string may use more than one type of delimiter to bracket information into “blocks.” For example, A string may use braces { }, parentheses ( ), and brackets [ ] as delimiters. A string is properly delimited if each right delimiter is matched with a preceding left delimiter of the same type in such a way that the either the resulting blocks of information are disjoint, or one of them is completely nested within the other. Write a program that uses a single stack to check whether a string containing braces, parentheses, and brackets is properly delimited.
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…
Log There was a storm recently on Jolibi village. The storm was so strong that some treesfell. There are some logs of varied length lying on the ground. The village ground canbe represented by a string of length N, where the i-th character is either 1 or 0. A singlelog is represented by consecutive characters of 1, and two different logs are separated byone or more 0. For example, for the string 1100010111, there are 3 logs. The first one atposition 1 to 2 with length 2, the second one at position 6 with length 1, and the thirdone at position 8 to 10 with length 3.As a carpenter, you want to take one of these logs home. Because you are the seniorcarpenter, you may take the longest log home. Determine the length of the longest log! Format InputThe first line contains an integer N, the length of the string. The next line contains a string of length N, which represents thevillage ground. Format OutputOutput an integer X, the length of the longest log. Constraints• 1 ≤ N ≤ 104• the i-th…
Write a regular expression for the set of strings over the alphabet {a, b} that have at least one a andat least one b. For example, aaaba and bbaba are strings in the set, but aaaa and bbb are not.
In C language, implement the following two functions that allow breaking a string into non-empty tokens using a given delimiter. For example, For a string "abc-EFG-hi", and a delimiter '-': the list of tokens is ["abc", "EFG", "hi"] For a string "abc-EFG---hi-", and a delimiter '-': the list of tokens is ["abc", "EFG", "hi"] For a string "abc", and a delimiter ' ': the list of tokens is ["abc"] For a string "++abc++", and a delimiter '+': the list of tokens is ["abc"] That is, we break the string using the given delimiter, and the tokens are only the non-empty substrings. 1. The function count_tokens gets a string str, and a char delim, and returns the number of tokens in the string separated by delim. int count_tokens(const char* str, char delim); For example count_tokens("abc-EFG--", '-') needs to return 2. count_tokens("++a+b+c", '+') needs to return 3. count_tokens("***", '*') needs to return 0. 2. The function get_tokens gets a string str, and a char delim, and returns the…
Create a subroutine that breaks down a noun-verb-object simple sentence into its component components. For example, the phrase "Mary walked the dog" is deconstructed as follows:Noun: MaryVerb: walkedObject: the dog The dog is the object.This function should be compatible with both StringBuilder and String objects.
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.
Taxi zum zum def taxi_zum_zum(moves): A taxicab cruising around the Manhattan street grid starts at the origin (0,0) of the infinite twodimensional lattice grid of all pairs of integers, denoted by ℤ2. This taxicab has a direction that is always one of the four main compass directions, initially heading north. The taxicab then faithfully executes the given sequence of moves, guaranteed to be a string made up of the characters 'L' for turning 90 degrees left (while standing in place), 'R' for turning 90 degrees right (ditto), and 'F'for moving one step forward towards the current heading. This function should return the final position of the taxicab in the integer grid coordinates of this infinitely spanning Manhattan. moves expected result 'RFRL' (1, 0) 'LFFLF' (-2, -1) 'LLFLFLRLFR' (1, 0) 'FR' * 1000 (0, 0) 'FFLLLFRLFLRFRLRRL' (3, 2)