Draw parse trees for nine strings in question one, using their grammars. For the following grammars,...

Draw parse trees for nine strings in question one, using their grammars.

For the following grammars, write the leftmost derivation for the strings given with each. Next to each derivation step, write the number of the rule used. Do not combine steps.
1. grammar (3 rules), Σ = {a, b}:

S -> aSbS | bSaS | ε

strings (3): ab, baab, bbaa

grammar (6 rules), Σ = {0, 1}:

S -> A1B

A -> 0A | ε

B -> 0B | 1B | ε

strings (3): 1, 0011, 01010

grammar (6 rules), Σ = { +, x, a, (, ) }

E -> E + T | T

T -> T x F | F

F -> (E) | a

strings (3): a, a x a, (a) + a x a,

grammar (4 rules), Σ = {(, ), [, ]}:

S -> (S) | [S] | SS | ε

strings (3): ( ), [ ] ( ), ( [ ] )

Solutions

Expert Solution

Answer:

venereology answered 9 months ago

Next > < Previous

Related Solutions

For the following grammars, write the leftmost derivation for the strings given with each. Next to...

For the following grammars, write the leftmost derivation for the strings given with each. Next to each derivation step, write the number of the rule used. Do not combine steps. grammar (6 rules), Σ = {0, 1}: S -> A1B A -> 0A | ε B -> 0B | 1B | ε strings (3): 1, 0011, 01010 grammar (6 rules), Σ = { +, x, a, (, ) } E -> E + T | T T -> T x...

Which of the following has two parse trees according to G?

Consider the following grammar: S ➝ A B C D A ➝ a A | c A | ε B ➝ b B | ε C ➝ a C | c D ➝ A | d | ε Which of the following has two parse trees according to G? a) a b) ac -- Correct Answer c) ε d) bc e) b

using java, parse a text file to answer the following question: -list sentences with the maximum...

using java, parse a text file to answer the following question: -list sentences with the maximum number of occurences of the word “the” in the whole file and also list the corresponding frequency. (cannot use hash maps) example output: the:3:The day had came to leave before the storm. What hit the back bumper of the car before the window cracked? The classroom doors where shut closed before the students open the project.

Draw PDA transition diagram for the following language: The set of strings over the alphabet {x,...

Draw PDA transition diagram for the following language: The set of strings over the alphabet {x, y} where 2 * (# of x's) = 3 * (#y's) That is, if we let nx be the number of x's and ny be the number of y's, then the strings in these language are those where 2nx = 3ny Try to find a PDA that is as simple and elegant as possible (do not convert from CFG). ------------------------------------------------------------------------------------------------------------------ USE Notation between transition:...

given a input file, parse it and answer the following frequency related questions, using java. -list...

given a input file, parse it and answer the following frequency related questions, using java. -list the most frequent word(s) in the whole file and its frequency. -list sentence(s) with the max. number of occurrences of the word “of” in the entire file and also list the corresponding frequency. program has two arguments; 1st : path to the input text file 2nd : name prefix for the output files ex. $ java assgn1 “./input.txt” “output” outputs: for each question create...

This is one question about 14-bit strings How many 14-bit strings that have more 0’s than...

This is one question about 14-bit strings How many 14-bit strings that have more 0’s than 1’s? How many 14-bit strings that have even number of 0’s? How many 14-bit strings that have no consecutive three 0’s in a row?

QWhich of the following are considered to be one of the top nine characteristics of a...

QWhich of the following are considered to be one of the top nine characteristics of a programming language (choose all that apply): o Simplicity o Recursive adaptation o Restricted aliasing o Semantic evaluation Q list six features of programming functionality provided by the plankalkül programming language. QWhat language(s) are direct predecessors to the PHP programming language? (choose any that apply): o Fortran I o Perl o Awk o ICON Q Based on the Von Neumann Architecture which of the following...

Using Python answer the following questions. 1. Describe the class of strings matched by the following...

Using Python answer the following questions. 1. Describe the class of strings matched by the following regular expressions. Provide examples that can be captured by the regular expression pattern. (a) [A-Za-z]+ (b) ^[A-Za-z]+.\d$ 2. Which of the following matches regexp /(very )+(thick )?use(ful|less) book/? Explain why. A. very thick book B. very very useful book C. thick useless book D. very useless book

1.) Using excel. A random number generator picks a number from one to nine in a...

1.) Using excel. A random number generator picks a number from one to nine in a uniform manner. X ~ _________ Graph the probability distribution. f(x) = _________ μ = _________ σ = _________ P(3.5 < x < 7.25) = _________ P(x > 5.67) P(x > 5|x > 3) = _________ Find the 90th percentile. 2) using excel A subway train on the Red Line arrives every eight minutes during rush hour. We are interested in the length of time...

I need to reverse strings with spaces using the nextLine() with Scanner in the following code:...

I need to reverse strings with spaces using the nextLine() with Scanner in the following code: package Chapter8; //To import the necessary libraries import java.util.Scanner; public class BackwardString { public static void main(String[] args) { //To read string from user input String input; Scanner scanner = new Scanner(System.in); System.out.print("Enter String here : "); input=scanner.next(); //To reverse passed string backward(input); //To close Scanner object scanner.close(); } //To reverse the input string private static void backward(String source) { int i, len =...

Subjects