Question

In: Computer Science

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.

  1. 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

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

S -> A1B

A -> 0A | ε

B -> 0B | 1B | ε

strings (3): 1, 0011, 01010

  1. 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,

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

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

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

Solutions

Expert Solution

Answer:


Related Solutions

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  
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...
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 a DFA for the following ( ∑ = {0,1}):                                 Set of all strings with.
Draw a DFA for the following ( ∑ = {0,1}):                                 Set of all strings with at most one consecutive pair of 1’s.
C Program: create a mini calculator with the following usage (using getopt to parse the command...
C Program: create a mini calculator with the following usage (using getopt to parse the command line arguments) Usage: minicalc [-a num] [-m num] [-x] value 1. The variable value is the starting value. 2. Value should be validated to be an integer between 1 and 50 inclusive. Error message and usage shown if not. 3. For the -m option num should be a positive integer between 1 and 10 inclusive. 4. For the -a option num should be a...
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
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT