1. Consider the regular grammar G given below: S → aS|aA|bB|λ A → aA|bS B →...

1. Consider the regular grammar G given below:

S → aS|aA|bB|λ

A → aA|bS

B → bB|aS

(a) Give a derivation for the strings aabbba and baaba

(b) Give an infinite language L such that L is not a subset of L(G)

Solutions

Expert Solution

(a)

aabbba

S -> (aS) -> a(aS) -> aa(bB) -> aab(bB) -> aabb(bB) -> aabbb(aS) -> aabbba() -> aabbba

baaba

S -> (bB) -> b(aS) -> ba(aS) -> baa(bB) -> baab(aS -> baaba( ) -> baaba

(c) please refer to the image below. We are constructing an NFA from the given relations. We add a starting state q and ending state f . Then we remove each intermidiary state and replacing the edges with their regular expressions until we have only q and f remaining in the NFA to get our regular expression

For part (b) we simply use our regular expression from (c) to construct a language which includes more than what our L(G) defines by including some extra language rules. All has been given in the pictures above

venereology answered 1 year ago

Next > < Previous

Related Solutions

Parent 1: AA Bb cc Parent 2: Aa Bb Cc A, B, and C are dominant....

Parent 1: AA Bb cc Parent 2: Aa Bb Cc A, B, and C are dominant. How many distinct phenotypes could be produced?

For a grammar G with the productions where G = ( {S, A, B}, {a, b},...

For a grammar G with the productions where G = ( {S, A, B}, {a, b}, S, P ) with productions S --> AB | bbbB, A --> b | Ab, B --> a.. 1.Show that the grammar G is ambiguous. 2.Give language L that is generated by G, L = L(G), in a formal expression (including a regular expression). 3.Can you construct an unambiguous grammar that is equivalent to G? Otherwise, show that G is inherently ambiguous.

Consider the context-free grammar G = ( {S}, {a, b}, S, P) where P = {...

Consider the context-free grammar G = ( {S}, {a, b}, S, P) where P = { S -> aaSb | aab }. Construct a NPDA M that such that L(M) = L(G). I would like the transition graph for this NPDA please.

Consider the reaction and associated equilibrium constant: aA(g)⇌bB(g), Kc = 1.9 Find the equilibrium concentrations of...

Consider the reaction and associated equilibrium constant: aA(g)⇌bB(g), Kc = 1.9 Find the equilibrium concentrations of A and B for a=2 and b=2. Assume that the initial concentration of A is 1.0 M and that no B is present at the beginning of the reaction. Find the equilibrium concentrations of A and B for a = 2 and b = 1. Assume that the initial concentration of A is 1.0 M and that no B is present at the beginning...

Consider the following reaction and associated equilibrium constant: aA(g)⇌bB(g), Kc = 4.0 Part A Find the...

Consider the following reaction and associated equilibrium constant: aA(g)⇌bB(g), Kc = 4.0 Part A Find the equilibrium concentrations of A and B for a=1 and b=1. Assume that the initial concentration of A is 1.0 M and that no B is present at the beginning of the reaction. Express your answers using two significant figures separated by a comma. [A], [B] = M Part B Find the equilibrium concentrations of A and B for a=2 and b=2. Assume that the...

Consider the following reaction and associated equilibrium constant: aA(g)⇌bB(g), Kc = 1.5 Part A Find the...

Consider the following reaction and associated equilibrium constant: aA(g)⇌bB(g), Kc = 1.5 Part A Find the equilibrium concentrations of A and B for a=1 and b=1. Assume that the initial concentration of A is 1.0 M and that no B is present at the beginning of the reaction. Express your answers using two significant figures separated by a comma. [A], [B] = ?M Part B Find the equilibrium concentrations of A and B for a=2 and b=2. Assume that the...

Given a grammar G, G = (Ν, Σ, Π, S), where Ν = { ... }...

Given a grammar G, G = (Ν, Σ, Π, S), where Ν = { ... } Σ = { ... } Π = { ... } S is ... For a string ... write (a) A leftmost derivation (b) A rightmost derivation

Consider the following reaction and associated equilibrium constant: aA(g)+bB(g)⇌cC(g), Kc = 5.0 Part A. Find the...

Consider the following reaction and associated equilibrium constant: aA(g)+bB(g)⇌cC(g), Kc = 5.0 Part A. Find the equilibrium concentrations of A, B, and C for a=1, b=1, and c=2. Assume that the initial concentrations of A and B are each 1.0 M and that no product is present at the beginning of the reaction. Part B. Find the equilibrium concentrations of A, B, and C for a=1, b=1, and c=1. Assume that the initial concentrations of A and B are each...

Simplify the grammar G. Does L(G) contain ε ? S -> A B C | B...

5. Consider the following tetrahybrid self-cross: Aa Bb Cc Dd X Aa Bb Cc Dd Calculate...

5. Consider the following tetrahybrid self-cross: Aa Bb Cc Dd X Aa Bb Cc Dd Calculate the probability for each of the following offspring. Show your work. Genotype Aa BB CC Dd Heterozygous for ALL FOUR genes Heterozygous for ANY gene Dominant phenotype for ALL FOUR traits GIVEN that an individual offspring has the dominant phenotype for all four traits, what is the probability that individual is heterozygous for all four genes? GIVEN that an individual offspring has the recessive...

Subjects