Question

S→aXbX | abX |aXb | ab X→aY | bY | a | b Y→aY | bY...

S→aXbX | abX |aXb | ab

X→aY | bY | a | b

Y→aY | bY | a | b | c

Is the language finite or infinite? Explain and Justify your answer

Homework Answers

Answer #1

Given,

S-> aXbX | abX | aXb | ab

X-> aY | bY | a | b

Y-> aY | bY | a | b | c

  • A language is a set of strings that can be derived from the given alphabet.
  • The strings in the language contain only terminals.
  • Here, 'a', 'b', 'c' are terminals, and 'S', 'X', 'Y' are non-terminals.
  • If the grammar products an infinite number of strings, the language is infinite.
  • If the grammar produces a finite number of strings, the language is finite.
  • Here, in this case, every nonterminal can be replaced with a terminal symbol or the combination of the terminal symbols like 'a', 'b', 'c', or 'ab'.
  • So the strings are countable.
  • As a result, the language is finite.


Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
find dy/dx by using implicit function theorem. (a) x=lny (b) x(x+y)=1 (c)ay^2+by+c=x (a, b, c are...
find dy/dx by using implicit function theorem. (a) x=lny (b) x(x+y)=1 (c)ay^2+by+c=x (a, b, c are constants)
when z=f(x,y), where tan(xyz)=x+y+z, find az/ax and az/ay
when z=f(x,y), where tan(xyz)=x+y+z, find az/ax and az/ay
2. (a) Let a,b ≥0. Define the function f by f(x)=(a+b+x)/3-∛abx Determine if f has a...
2. (a) Let a,b ≥0. Define the function f by f(x)=(a+b+x)/3-∛abx Determine if f has a global minimum on [0,∞), and if it does, find the point at which the global minimum occurs. (b) Show that for every a,b,c≥0 we have (a+b+c)/3≥∛abc with equality holding if and only if a=b=c. (Hint: Use Part (a).)
(a) Let A ⊂ R be open and B ⊂ R. Define AB = {xy ∈...
(a) Let A ⊂ R be open and B ⊂ R. Define AB = {xy ∈ R : x ∈ A and y ∈ B}. Is AB necessarily open? Why? (b) Let S = {x ∈ R : x is irrational}. Is S closed? Why? Thank you!
Let t and s be transformations of the plane such that t(x, y) = (x+a, y+b)...
Let t and s be transformations of the plane such that t(x, y) = (x+a, y+b) and s(x, y) = (x+c, y+d) where a, b, c, and d are Real numbers. Let ?(?1, ?1) and ?(?2, ?2) be any two points in the plane. Show that (s ◦ t)(x, y) is an isometry.
1. Consider the relations R = {(x,y),(y,z),(z,x)} and S = {(y,x),(z,y),(x,z)} on {x, y, z}. a)...
1. Consider the relations R = {(x,y),(y,z),(z,x)} and S = {(y,x),(z,y),(x,z)} on {x, y, z}. a) Explain why R is not an equivalence relation. b) Explain why S is not an equivalence relation. c) Find S ◦ R. d) Show that S ◦ R is an equivalence relation. e) What are the equivalence classes of S ◦ R?
Suppose you have two numbers x, y ∈ Q (that is, x and y are rational...
Suppose you have two numbers x, y ∈ Q (that is, x and y are rational numbers). a) Use the formal definition of a rational number to express each of x and y as the ratio of two integers. Remember, x and y could be different numbers! (b) Use your results from (a) to show that xy must also be a rational number. Carefully justify your answer, showing how it satisfies the formal definition of a rational number. (2) Suppose...
q.1.(a) The following system of linear equations has an infinite number of solutions x+y−25 z=3 x−5 ...
q.1.(a) The following system of linear equations has an infinite number of solutions x+y−25 z=3 x−5 y+165 z=0    4 x−14 y+465 z=3 Solve the system and find the solution in the form x(vector)=ta(vector)+b(vector)→, where t is a free parameter. When you write your solution below, however, only write the part a(vector=⎡⎣⎢ax ay az⎤⎦⎥ as a unit column vector with the first coordinate positive. Write the results accurate to the 3rd decimal place. ax = ay = az =
Given the function f (x, y) = ax^2 2 + 2xy + ay.y 2-ax-ay. Take for...
Given the function f (x, y) = ax^2 2 + 2xy + ay.y 2-ax-ay. Take for a an integer value that is either greater than 1 or less than -1, and then determine the critical point of this function. Then indicate whether it is is a local maximum, a local minimum or a saddle point. Given the function f (x, y) = ax^2 +2 + 2xy + ay^2-2-ax-ay. Take for a an integer value that is either greater than 1...
Let S denote the set of all possible finite binary strings, i.e. strings of finite length...
Let S denote the set of all possible finite binary strings, i.e. strings of finite length made up of only 0s and 1s, and no other characters. E.g., 010100100001 is a finite binary string but 100ff101 is not because it contains characters other than 0, 1. a. Give an informal proof arguing why this set should be countable. Even though the language of your proof can be informal, it must clearly explain the reasons why you think the set should...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT