Question: Did I do this correctly? Question: Construct context-free grammars that generate the following languages (give your answers as a set of rules): {a n b

Did I do this correctly?

Question:

Construct context-free grammars that generate the following languages (give your answers as a set of rules):

  1. {anbn+kak{a,b}|n0,k0}

Answer:

S | aAbB | AbBa

A | aAb

B | bBa

Possible strings to test on:

n = 0, k = 2

bbaa

SAbBabBabbBaabbaabbaa

n =2, k = 1

aabbba

SaAbBaaAbbBaabbbBaaabbbaaabbba

n = 1, k = 3

abbbbaaa

SaAbBabBabbBaabbbBaaabbbbBaaaabbbbaaaabbbbaaa

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

Q:

Did I do this problem correctly? Question: Construct context-free grammars that generate the following languages (give your answers as a set of rules): {a k w|w {a,b} ,|w|=k,k0} Answer: S | A A | aAB...

Q:

"Fortran, Algol and Lisp invented most programming language concepts 50 years ago; adding the concept of object-orientation suffices to explain all programming languages to date". To what extent is...

Q:

In this question you will be asked to reflect on a project you have been involved in or observed, in which a design evolved, or could have evolved, through applying a theory of user behaviour. You...

Q:

Create four language guidelines: two for Spanish and two for English, each with a descriptive and required component. This chapter is a brief introduction to modern linguistics and to topics that...

Q:

ttth Suppose that the sequence of bags {Bn | n N} is recursively enumerated by the computable function e(n, x) = fn(x), [7 marks] Hence prove that the set of all recursive bags cannot be recursively...

Q:

can someone solve this Modern workstations typically have memory systems that incorporate two or three levels of caching. Explain why they are designed like this. [4 marks] In order to investigate...

Q:

Consider the trigonometric series a0 2 + X r=1 (ar cos rx + br sin rx) where a0, a1, a2, . . . and b1, b2, . . . are constants and suppose that f(x) is a periodic function of x with period 2. (a)...

Q:

This question concerns lexical grammars. (a) Tree Adjoining Grammars contain two types of elementary tree. (i) What are these trees called? [1 mark] (ii) If one were building a grammar for English...

Q:

In a Hopfield neural network configured as an associative memory, with all of its weights trained and fixed, what three possible behaviours may occur over time in configuration space as the net...

Q:

dee complete please help Complexity Theory (a) Defifine the set of Boolean expressions 2CNF and the language 2SAT over them. (b) For a Boolean expression in 2CNF, let G() be the directed graph with...

Q:

Before accepting a large shipment of bolts, the director of an elevator construction project checks the tensile strength of a simple random sample consisting of 20 bolts. She is concerned that the...

Q:

A synthesis of triacylglycerols has been described that begins with the substance shown. Outline a series of reactions suitable for the preparation of a triacylglycerol of the type illustrated in the...

Q:

lets say you are now 1 0 years into a 2 0 0 , 0 0 0 mortgage ( at 4 . 8 0 APR, originially for 3 6 0 months ) and you decide to sell the house. When you sell the house you will need to pay whatever...

Q:

based on the table Based on the table below, evaluate f ( 8 ) . f ( 8 ) = f ( 2 . 3 ) = f ( 1 0 ) =

Q:

Assume that the banking system has total reserves of $100 billion. Assume also that required reserves are 10 percent of checking deposits and that banks hold no excess reserves and households hold no...

Q:

As shown in Figure 3, the overall labor-force participation rate of men declined between 1970 and 2000. At the same time, the labor-force participation rate of women increased sharply. This overall...

Q:

The Bureau of Labor Statistics announced that in February 2008, of all adult Americans, 145,993,000 were employed, 7,381,000 were unemployed, and 79,436,000 were not in the labor force. Use this...