Question

Consider the following grammar. Nonterminals are lowercase and terminals are uppercase. s -> c A c...

Consider the following grammar. Nonterminals are lowercase and terminals are uppercase.
s -> c A
c -> c B | B


Which of the following sentences is in the language generated by the grammar?

a) BAA

b) BBBA

c) BBAAAAA

d) none of the above

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1 

b) BBBA

Explanation:
-------------
s
-> cA
-> cBA
-> cBBA
-> BBBA
so, BBBA is generated by this grammar
this language generates strings in the pattern of one or more B's and then ends with a single A
but BAA ends with two A's and BBAAAAA ends with 5 A's. these two can't be generated by this grammar


0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Question 1 Consider the following grammar G: S ➝ A B C | A C |...
Question 1 Consider the following grammar G: S ➝ A B C | A C | A | B A ➝ a B B ➝ b C | a C ➝ c D D ➝ d A Recall that a non-terminal A is reachable if there is a derivation starting from S in which A appears: S ⇒* x A y holds for some x and y which are sequences of terminals and non-terminals (possibly empty). For example, if there...
Consider the following grammar (A and B are non-terminals) A → A a | B |...
Consider the following grammar (A and B are non-terminals) A → A a | B | B d B → b d | b Are there any ambiguities? If so, please give an example.
Automata Theory and Formal Languages Problems 1: Consider the following two grammars. Grammar G1- S →...
Automata Theory and Formal Languages Problems 1: Consider the following two grammars. Grammar G1- S → aSb / ∈ Grammar G2- S → aAb / ∈, A → aAb / ∈ a. is G1=G2 b. What is the grammar generated by the expression Problem 2: Let us consider the grammar. G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε } ) Derive aaabbb Problem 3: Suppose we have the following grammar. G: N...
Give a right-linear grammar to generate each of the following: (a) All identifiers of lowercase letters...
Give a right-linear grammar to generate each of the following: (a) All identifiers of lowercase letters that either begin or end in a (or both). (b) The set of all integers and real numbers in decimal notation. No leading zeros should be generated and real numbers must have at least one digit on both sides of the decimal point. For instance, 3, +3, -3, 0, +0, -0, 0.00328, -100.46, and +100.000 are in the language, but 100., +, -, 003...
Given the following grammar G = (V, T, S, P) where S is the starting symbol....
Given the following grammar G = (V, T, S, P) where S is the starting symbol. (1) S → aS (2) S → aD (3) D → bD (4) D → λ (a) Give two strings of different lengths that are generated from G (b) Give two strings that cannot be generated from G (c) What is the language generated by G, that is L(G)
Convert the grammar G = ({S,A,B,C},{a,b},P,S), where P is given below, into the Chomsky Normal Form....
Convert the grammar G = ({S,A,B,C},{a,b},P,S), where P is given below, into the Chomsky Normal Form. S −→ AaA | AB A −→ BB | bAA | ε B −→ bS | b | ε
Consider the following grammar S -> A M M -> S | A -> a E...
Consider the following grammar S -> A M M -> S | A -> a E | b A A E -> a B | b A | B -> b E | a B B Show a derivation for the string a b a a. Start with S => A M => ... and in each step replace one nonterminal by the right-hand side of a grammar rule until you end up with the symbols a b a a...
Consider the grammar G with productions as follows: S → AD | BC A → a...
Consider the grammar G with productions as follows: S → AD | BC A → a B → b C → a | AS | BE D → b | BS | AF E → CC F → DD Use the CYK algorithm to test membership of abbaba.
A bullet with mass m(lowercase m) is fired into a block of wood with mass M(uppercase...
A bullet with mass m(lowercase m) is fired into a block of wood with mass M(uppercase M), suspended like a pendulum, and makes a completely inelastic collision with it. After the impact of the bullet, the block swings up to a maximum height h. Given the values of h = 5.00 cm = 0.0500 m, m = 6.75 g = 0.00675 kg, and M = 2.50 kg, (a) What is the (initial) velocity v_x of the bullet in m/s? (b)...
1. Draw a GTG (generalized transition graph) for the following right-linear regular grammar. S -> abA...
1. Draw a GTG (generalized transition graph) for the following right-linear regular grammar. S -> abA A -> baB B->aA | bb a)  Find a left-linear grammar for the language in the previous question.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT