Compute the regular expression, Mathematics

1. Consider the following context free grammar G with start symbol S (we write E for the empty string, epsilon):

S ---> bB | aSS

A ---> aB | bAA

B ---> E | bA | aS

a. Describe L(G), i.e. complete the following definition: L(G) = { w ∈ {a, b}* | ...

b. Show that G is ambiguous.

2. Give a context free grammar for regular expressions over the alphabet Σ = {0, 1}.

Use the definition of a regular expression given on page 64 of the text.

3. Let L1 and L2 be regular languages and let L = {xy | x ∈ L1 and y ∈ L2 and |x| = |y|}.

a. Is L regular? Answer clearly YES or NO and justify/prove your answer.

b. Is L context free? Answer clearly YES or NO and justify/prove your answer.

4. Let L = {w ∈ {0, 1}* | (the number of 0's in w) mod 3 = 2}. Give a state diagram in the style of the text for a TM that recognizes, but does not decide, L.

5. Turing machines can be considered computers of functions and not just accepters of strings. The function parameter or input is what is written on the tape when the TM starts and its value or output is what is written on the tape when it halts. If it does not halt, the function it computes is not defined for that particular parameter.

Consider the function f(n) = 8n + 5. Assume that n is written on the tape in binary (just 0's and 1's, perhaps with leading 0's) and that the value computed is also written in binary. We don't care whether the value computed has unnecessary leading 0's or not. All numbers are considered unsigned.

Describe at a high level a TM to compute this function.

6. Let L = { | R is a regular expression describing a language that contains at least one string with the substring 111}.

Show that L is decidable.

Questions are shown in the order received.

1. Q: Should here be a * after the {0, 1} in question 2?

A: No. S is an alphabet, not a language. When we speak of a string over S that is the same as saying a string in S*

2. Q: In question 3, does "the number of 0's in w mod 3 = 2" mean you count the 0's in the string and mod that number by 3?

A: Yes. I've now put parentheses around part of it to make it clear; as in: (the number of 0's in w) mod 3

Posted Date: 3/6/2013 4:22:21 AM | Location : United States







Related Discussions:- Compute the regular expression, Assignment Help, Ask Question on Compute the regular expression, Get Answer, Expert's Help, Compute the regular expression Discussions

Write discussion on Compute the regular expression
Your posts are moderated
Related Questions
(a) Assume that A is a m 1 ×m 2 matrix and B is a m 2 ×m 3 matrix. How many multiplications are required to calculate the matrix product AB? (b) Given that A 1 is a 20 × 50 m

We will firstly notice the undamped case. The differential equation under this case is, mu'' + ku  = F(t) It is just a non-homogeneous differential equation and we identify h

From past experience a machine is termed to be set up correctly on 90 percent of occasions.  If the machine is set up correctly then 95 percent of good parts are expected however i

40.783-75

For the layman, a "function" indicates a relationship among objects. A function provides a model to describe a system. Economists refer to deman

express the area of a square with sides of length 5ab as monomial

como realizar la i elevavda a la 243

A man invests rs.10400 in 6%shares at rs.104 and rs.11440 in 10.4% shares at rs.143.How much income would he get in all??

Divides a given line segment internally in the ratio of 1:3 Construction : i )Draw a ray AX making an acute angle with AB. ii) Mark 4 points at equal distance. on AX Let

Q. What is Box-and-Whisker Plot? Ans. Line graphs or stem-and-leaf plots become difficult to manage when there is a large amount of data. Box-and-whisker plots help summa