Purchase Solution

Explain the language accepted by the given grammar

Not what you're looking for?

Ask Custom Question

Given the following grammar, where upper-case letters are non-terminals and lower-case letters are terminals. Which strings are valid?

Attachments
Purchase this Solution
Solution Summary

In this solution I explain how a given grammar, expressed in BNF-type notation, generates a series of strings. In particular, I show which strings are accepted and which are rejected by the given grammar.

Solution Preview

The best approach for this problem is to get a good understanding of what the grammar is accepting. Starting from S there are two paths: A and B. Let's look at each path separately.

The first A rule is:

A -> aCbA

C is defined as simply "ba" so we can substitute that in and rewrite the first A rule as:

A -> ababA

Notice that this is recursive so it would never stop unless it hits the terminating case. That is the second A rule. The second A rule is:

A -> ab

So for the A path we can describe the set ...

Purchase this Solution
Free BrainMass Quizzes
Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.

Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

C# variables and classes

This quiz contains questions about C# classes and variables.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

Basic Networking Questions

This quiz consists of some basic networking questions.

View More Free Quizzes
Related BrainMass Solutions

  • What is Grammar and Leaner's Grammar

    , which will explain the facts of the language.

  • Compilers: Language defined by a grammar

    191928 Compilers: Language defined by a grammar Describe the language defined by the following grammar: :: = | :: = , :: = A The language defined by the given grammar consists of only two statements

  • Language of Words:Strings, Pseudocode and Recursive Function

    ') { String toLookFor = SubString(str, 0, len-2); // str[0 ... len-2] return isIn(toLookFor); } else // Given string can not be generated by the rules of given grammar.

  • Importance of Grammar

    Supporting data is given about the value of grammar.

  • Language Acquisition

    Skinner's explanation of language was that any acquisition was due to a learning process involving the shaping of grammar into a correct form by the re-enforcement of other stimulus, correct grammar is positively re-enforced and will be used in the future

  • Child Growth and Development

    Nativists view that there are some "hidden assumptions" or biases (Yang, 1994) that allow children to quickly figure out what is and isn't possible in the grammar of their native language, and allow them to master that grammar by the age of three (Pinker

  • Theories of Language Acquisition

    As Chomsky pondered the complex intricacies of children's development of grammar, he concluded that language acquisition could only be accounted for by an innate, biological language acquisition device (LAD) or system.

  • Three language aquisition theories

    on the success of their attempts to communicate from non verbal cues given by the teacher.

  • Generic Programming Language example

    Write a grammar for the language consisting of strings that have n copies of the letter a followed by the same number of copies of the letter b, where n > 0.

View More Related Solutions