Question

In: Computer Science

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)

(c) Give a regular expression that describes the language 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


Related Solutions

Find Consider the following context-free grammar G: S --> T#T T --> C A --> aA...
Find Consider the following context-free grammar G: S --> T#T T --> C A --> aA | epsilon B --> bB | epsilon C --> cC C --> c a) Give the set of unproductive symbols in G? b) Give an equivalent grammar without useless symbols.
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...
Simplify the grammar G. Does L(G) contain ε ? S -> A B C | B a B A -> a A | B a C | a a a B -> b B b | a | D C -> C A | A C D -> ε
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT