Compute the regular expression, Mathematics

Assignment Help:

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


Related Discussions:- Compute the regular expression

Interval of convergence - sequences and series, Interval of Convergence ...

Interval of Convergence After that secondly, the interval of all x's, involving the endpoints if need be, for which the power series converges is termed as the interval of conv

Difference between absolute and relative in the definition, Difference betw...

Difference between absolute and relative in the definition Now, let's talk a little bit regarding the subtle difference among the absolute & relative in the definition above.

Basic, is 1/6 same as six times less

is 1/6 same as six times less

TRIANGLES, ABCD is a trapezium AB parallel to DC prove square of AC - squar...

ABCD is a trapezium AB parallel to DC prove square of AC - square of BCC= AB*

Elimination, Eliment t from following equations v=u+at s=ut+1/2at^2

Eliment t from following equations v=u+at s=ut+1/2at^2

The bionomial theorem for rational index, use the bionomial theorem to expa...

use the bionomial theorem to expand x+2/(2-X)(WHOLE SQUARE 2)

Math, 1+3+5+7+9+11+13+15+17+19

1+3+5+7+9+11+13+15+17+19

Find a minimum cost spanning arborescence rooted, Find a minimum cost spann...

Find a minimum cost spanning arborescence rooted at r for the digraph shown below, using the final algorithm shown in class.  Please show your work, and also give a final diagram w

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd