Write a regular expression defining strings

Assignment Help Basic Computer Science
Reference no: EM13287328

1.Write a regular expression defining strings that begin with an a and end with a b and can contain any number (including zero) of c's or d's in the middle. Every c that is in the string must be followed by at least one d.
2. Construct a deterministic finite state automaton with no more than four states that accepts the language defined by the regular expression in problem 1.
3.  Define an unambiguous context free grammar that generates the language of strings containing a series of a's followed by a series of b's followed by a series of c's concluding with a series of d's. The number of a's must be exactly the sames as the number of d's and the number of b's must be exactly the same as the number of c's. The strings must contain at least of instance one each of the four letters. Examples of valid stings are:
aaabbccddd abbbcccd
Is this a regular language? Explain your answer.
4. Provide a left-most derivation of the second example shown in the previous problem and a parse tree that corresponds to that derivation.
5. Define a language that is not a regular language using a context-free grammar that is not ambiguous. The alphabet of the language must contain at least five characters. Describe in English the strings of the language. Choose any string that is in the language and demonstrate that it is in the language by showing the left-most derivation that derives it. Draw the parse tree that corresponds to the left-most derivation. Give an example of one string that is not in the language.

Reference no: EM13287328

Questions Cloud

Jewelers company might derive from a new system : Suggest at least five (5) expected business benefits that Especially for You Jewelers company might derive from a new system. Provide a rationale for your suggestions.
What is the expected return on the portfolio : The following information is available in general and about investments in stocks J and K.
Calculate next year ending receivables balance : A firm is planning to lower its ACP by ten days next year. Receivables are currently $15M on credit sales of $120M Credit sales are expected to grow by 20% next year. Calculate next year's ending receivables balance (make calculations using ending..
Find the volume of the person that is above the water : A person with a mass of 71.6 kg and a volume of 0.089 m3 floats quietly in water. find the volume of the person that is above the water
Write a regular expression defining strings : 1.Write a regular expression defining strings that begin with an a and end with a b and can contain any number (including zero) of c's or d's in the middle. Every c that is in the string must be followed by at least one d.
What is the distance to the center of the object : A distance away from a uniformly charged spherical object, the magnitude of the electric field is 575V/m and the electric potential is 3.50kV. What is the distance to the center of the object
Find the composition of this hot vaporized material : As the fragment falls through the atmosphere, it is heated and some of the material is vaporized, find the composition of this hot vaporized material from the light it emits
What do you know about PETA : What do you know about PETA? How do you feel about the way in which they conduct their beliefs? What were your impressions of the way they dealt with KFC?What do you know about PETA? How do you feel about the way in which they conduct their beliefs? ..
Small businesses and multinational corporations : How does strategic planning differ between small businesses and multinational corporations? How is strategic planning different between public-sector and private-sector organizations?

Reviews

Write a Review

 

Basic Computer Science Questions & Answers

  Write a conversion program that prompts the user

Write a conversion program that prompts the user from which unit she/he wants to convert (gallon to liters, miles to Km, celsius to fahrenheit) . You should write three different methods.

  Write and explain the definition of composition in c++

Write and explain the definition of composition in C++ and how it is useful in writing object-oriented programming. Also, explain how it is different from inheritance and how both inheritance and composition are useful in developing object-oriente..

  Full-duplex trunk between end office-intermediate switch

In a simple telephone network comprising of two end offices and one intermediate switch with 1-MHZ full-duplex trunk between each end office and intermediate switch.

  Explain benefits of a global market

What are some of the benefits of a global market and why? List at least 2 benefits, weighing any short-term and long-term impacts.

  New century develop a new information system

New Century Wellness Group offers a holistic approach to health care with an emphasis on preventive medicine as well as traditional medical care. In your role as an IT consultant, you will help New Century develop a new information system

  How silicon-based semiconductors revolutionized computing

New materials frequently lead to new technologies that change society. Describe how silicon-based semiconductors revolutionized computing.

  True or false on computer science

True or False 1. If a computer uses hardwired control, the microprogram determines the instruction set for the machine.

  Differentiating unix and window traceroute

Compare and contrast differences between Unix (or Linux) and Window Traceroute. All codes for each ICMP error message are not completely listed and explained.

  Explain how to structure worksheet including titles

Explain how you will structure the worksheet, including the titles, column headings, and formulas to calculate the time it takes to make each size of cage.

  How code an interactive hangman game using string method

How do you code an interactive hangman game using the string method

  Declare a delegate using the keyword delegate

How are these examples of predefined control events and its usage in programming•Delegate-Object that contains a reference to a method

  People and organization responsible for bumping problems

Answer from the perspective of the airlines and from the perspective of the customers. What people, organization, and technology factors are responsible for excessive bumping problems?"

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