1. (Decidable languages) (c) (Prefix of a generated string) A string w is called a prefix...

Question

Question

1. (Decidable languages)

(c) (Prefix of a generated string) A string w is called a prefix of string s if s starts with w.

i. Give a regular expression for all strings over alphabet Σ for which w is a prefix.

ii. Let L = {(G, w) | G is a CFG, w is a string, and w is a prefix of some string s generated by G}.

Answer 1

Answer #1

i)

The regular expression for all strings over alphabet Σ for which w is a prefix is given as:

w . (0 + 1)*

ii)

Since there is no question being asked in this part, I am not answering it. Kindly provide additional details.

Answer 2

Similar Homework Help Questions

determine if the language is regular, context-free, Turing-decidable, or undecidable. For languages that are regular, give...

determine if the language is regular, context-free, Turing-decidable, or undecidable. For languages that are regular, give a DFA that accepts the language, a regular expression that generates the language, and a maximal list of strings that are pairwise distinguishable with respect to the language. For languages that are context-free but not regular, prove that the language is not regular and either give a context- free grammar that generates the language or a pushdown automaton that accepts the language. You need...
Give regular expressions generating the languages of 1. {w over the alphabet of {0, 1} | w is any string except 11 and 1...

Give regular expressions generating the languages of 1. {w over the alphabet of {0, 1} | w is any string except 11 and 111} 2. {w over the alphabet of {0, 1} | w contains at least two 0’s and at most one 1} 3. {w over the alphabet of {0, 1} | the length of w is at most 9} 4. {w over the alphabet of {0, 1} | w contains at least three 1 s} 5. {w over...
Give a regular expression generating the following languages over the alphabet {a,b}: {w | w is...

Give a regular expression generating the following languages over the alphabet {a,b}: {w | w is any string except aa and bbb}

Give a regular expression for these languages i) {w| w is a word of the alphabet...

Give a regular expression for these languages i) {w| w is a word of the alphabet = {0,1} that represents an integer in a binary form that is a multiple of 4} ii) {w belongs to {0,1,2}* | w contains the string ab exactly 2 times but not at the end} iii) { w belongs to {0,1,2}* | w=uxvx that x belongs to {0,1,2} u,v belongs to {0,1,2}* and there isn't any string y in the sequence v that x<y}
Give a regular expression that generates C In certain programming languages, comments appear between delimiters such...

Give a regular expression that generates C In certain programming languages, comments appear between delimiters such as /# and #. Let C be the language of all valid delimited comment strings. A mem- ber of C must begin with /# and end with #/ but have no intervening #. For simplicity, assume that the alphabet for Cis Σ {a, b, /
(a) Give 2 strings that are members of language specified by the regular expression (0+ 1)∗...

(a) Give 2 strings that are members of language specified by the regular expression (0+ 1)∗ but are not members of the language specified by 0∗ + 1∗ . Then give 2 strings that are members of both languages. Assume the alphabet is Σ = {0, 1}. (b) For each of the following languages specified by regular expressions, give 2 strings that are members and 2 strings that are not members (a total of 4 strings for each part). Assume...

Regular expressions, DFA, NFA, grammars, languages Regular Languages 4 4 1. Write English descriptions for the...

Regular expressions, DFA, NFA, grammars, languages Regular Languages 4 4 1. Write English descriptions for the languages generated by the following regular expressions: (a) (01... 9|A|B|C|D|E|F)+(2X) (b) (ab)*(a|ble) 2. Write regular expressions for each of the following. (a) All strings of lowercase letters that begin and end in a. (b) All strings of digits that contain no leading zeros. (c) All strings of digits that represent even numbers. (d) Strings over the alphabet {a,b,c} with an even number of a's....
Let S = {0,1}. Show that the problem of determining whether a CFG generates some string...

Let S = {0,1}. Show that the problem of determining whether a CFG generates some string in 1* is decidable. In other words, show that { <G>G is a CFG over {0,1} and 1* n L(G) != 0 }
1(a)Draw the state diagram for a DFA for accepting the following language over alphabet {0,1}: {w...

1(a)Draw the state diagram for a DFA for accepting the following language over alphabet {0,1}: {w | the length of w is at least 2 and has the same symbol in its 2nd and last positions} (b)Draw the state diagram for an NFA for accepting the following language over alphabet {0,1} (Use as few states as possible): {w | w is of the form 1*(01 ∪ 10*)*} (c)If A is a language with alphabet Σ, the complement of A is...

Additional 9-13 Prove that the language {w#w|w is a string over the alphabet {a,b,c}} is not...

Additional 9-13 Prove that the language {w#w|w is a string over the alphabet {a,b,c}} is not regular Tip: here are some strings in that language: abbc#abbc a#a aaa#aaa aaab#aaab cab#cab