DISCRETE MATHEMATICS LOOSELEAF
8th Edition
ISBN: 9781264309689
Author: ROSEN
Publisher: MCG
expand_more
expand_more
format_list_bulleted
Videos
Question
Chapter 13, Problem 3RQ
To determine
To define a type 1 grammer.
To determine
Example of a grammer that is not type 1 grammer.
To determine
To define a type 2 grammer.
To determine
Example of a grammer that is not type 2 grammer but is a type 1 grammer.
To determine
To define a type 2 grammer.
To determine
Example of a grammer that is not type 3 grammer but is a type 2 grammer.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
Give context-free grammars to generate the following languages:
(a) L = {vuvkw : u, v, w E {0, 1}*, |u| = |w| = 2}
(b) L2 = {a"b"&d² :n+ m = k + l}
(c) L3 = {w : na(w) > ns(w) + 1}
(3) Give a grammar
G =(V.2,5, P), whereV =14, B,C;, =;a,b;,S =4, P: A- a4|bB, B- bC|aB,C aB|aC|2.
(a) Is G a regular grammar? Why?
(b) Find an nfa which accepts the language L(G).
(c) Find the regular expression r associated with the language accepted by the above nfa.
(d) Find regular language L(r) from the above r.
d, e, f
Chapter 13 Solutions
DISCRETE MATHEMATICS LOOSELEAF
Ch. 13.1 - Exercises 1-3 refer to the grammar with start...Ch. 13.1 - Exercises 1-3 refer to the grammar with start...Ch. 13.1 - Prob. 3ECh. 13.1 - Let G=(V,T,S,P) be the phrase-structure grammar...Ch. 13.1 - Prob. 5ECh. 13.1 - Prob. 6ECh. 13.1 - Prob. 7ECh. 13.1 - Show that the grammar given in Example 5 generates...Ch. 13.1 - Prob. 9ECh. 13.1 - Prob. 10E
Ch. 13.1 - Construct a derivation of 021222 in the grammar...Ch. 13.1 - Show that the grammar given in Example 7 generates...Ch. 13.1 - s13. Find a phrase-structure grammar for each of...Ch. 13.1 - Find a phrase-structure grammar for each of these...Ch. 13.1 - Find a phrase-structure grammar for each of these...Ch. 13.1 - Construct phrase-structure grammars to generate...Ch. 13.1 - Construct phrase-structure grammars to generate...Ch. 13.1 - Construct phrase-structure grammars to generate...Ch. 13.1 - Prob. 19ECh. 13.1 - A palindrome is a string that reads the same...Ch. 13.1 - Let G1 and G2 be context-free grammars, generating...Ch. 13.1 - Prob. 22ECh. 13.1 - Construct derivation trees for the sentences in...Ch. 13.1 - Let G be the grammar with V={a,b,c,S};T={a,b,c} ;...Ch. 13.1 - Prob. 25ECh. 13.1 - Prob. 26ECh. 13.1 - Prob. 27ECh. 13.1 - a) Explain what the productions are in a grammar...Ch. 13.1 - Prob. 29ECh. 13.1 - a) Construct a phrasestructure grammar for the set...Ch. 13.1 - Give production rules in Backus-Naur form for an...Ch. 13.1 - Prob. 32ECh. 13.1 - Prob. 33ECh. 13.1 - Prob. 34ECh. 13.1 - Prob. 35ECh. 13.1 - Prob. 36ECh. 13.1 - Prob. 37ECh. 13.1 - Prob. 38ECh. 13.1 - Prob. 39ECh. 13.1 - Prob. 40ECh. 13.1 - Prob. 41ECh. 13.1 - Let G be a grammar and let R be the relation...Ch. 13.2 - Draw the state diagrams for the finite-state...Ch. 13.2 - Give the state tables for the finite-state machine...Ch. 13.2 - Find the output generated from the input string...Ch. 13.2 - Find the output generated from the input string...Ch. 13.2 - Find the output for each of these input strings...Ch. 13.2 - Find the output for each of these input strings...Ch. 13.2 - Construct a finite-state machine that models an...Ch. 13.2 - Prob. 8ECh. 13.2 - Construct a finite-state machine that delays an...Ch. 13.2 - Construct a finite-state machine that changes...Ch. 13.2 - Construct a finite-state machine for the log-on...Ch. 13.2 - Construct a finite-state machine for lock that...Ch. 13.2 - Construct a finite-state machine for a toll...Ch. 13.2 - Construct a finite-state machine for entering a...Ch. 13.2 - Construct a finite-state machine for a restricted...Ch. 13.2 - Construct a finite-state machine that gives an...Ch. 13.2 - Prob. 17ECh. 13.2 - Construct a finite-state machine that determines...Ch. 13.2 - Construct a finite-state machine that determines...Ch. 13.2 - Prob. 20ECh. 13.2 - Prob. 21ECh. 13.2 - Find the output string generated by the Moore...Ch. 13.2 - Prob. 23ECh. 13.2 - Construct a Moore machine that gives an output of...Ch. 13.2 - Prob. 25ECh. 13.3 - Prob. 1ECh. 13.3 - 2. Show that if A is a set of strings, then.
Ch. 13.3 - Find all pairs of sets of strings A and B for...Ch. 13.3 - Show that these equalities hold. a) {}*={} b)...Ch. 13.3 - Prob. 5ECh. 13.3 - Prob. 6ECh. 13.3 - Prob. 7ECh. 13.3 - Prob. 8ECh. 13.3 - Prob. 9ECh. 13.3 - Determine whether the string 01001 is in each of...Ch. 13.3 - Determine whether each of these strings is...Ch. 13.3 - Determine whether each of these strings is...Ch. 13.3 - Determine whether all the strings in each of these...Ch. 13.3 - Show that if M=(S,I,f,so,F) is a deterministic...Ch. 13.3 - Given a finite-state automaton M=(S,I,f,so,F) ,...Ch. 13.3 - In Exercises 16—22 find the language recognized by...Ch. 13.3 - In Exercises 16—22 find the language recognized by...Ch. 13.3 - Prob. 18ECh. 13.3 - Prob. 19ECh. 13.3 - In Exercises 16—22 find the language recognized by...Ch. 13.3 - In Exercises 16—22 find the language recognized by...Ch. 13.3 - Prob. 22ECh. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Prob. 27ECh. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Prob. 29ECh. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Prob. 33ECh. 13.3 - Prob. 34ECh. 13.3 - Prob. 35ECh. 13.3 - Prob. 36ECh. 13.3 - Prob. 37ECh. 13.3 - Prob. 38ECh. 13.3 - Prob. 39ECh. 13.3 - Use Exercise 39 finite-state automata constructed...Ch. 13.3 - Prob. 41ECh. 13.3 - Prob. 42ECh. 13.3 - Prob. 43ECh. 13.3 - Prob. 44ECh. 13.3 - Prob. 45ECh. 13.3 - In Exercises 43-49 find the language recognized by...Ch. 13.3 - Prob. 47ECh. 13.3 - In Exercises 43-49 find the language recognized by...Ch. 13.3 - Prob. 49ECh. 13.3 - Find a deterministic finite-state automaton that...Ch. 13.3 - Prob. 51ECh. 13.3 - Find a deterministic finite-state automaton that...Ch. 13.3 - Find a deterministic finite-state automaton that...Ch. 13.3 - Find a deterministic finite-state automaton that...Ch. 13.3 - Find a deterministic finite-state automaton that...Ch. 13.3 - Find a nondeterministic finite-state automaton...Ch. 13.3 - Prob. 57ECh. 13.3 - Prob. 58ECh. 13.3 - Prob. 59ECh. 13.3 - Prob. 60ECh. 13.3 - Prob. 61ECh. 13.3 - Prob. 62ECh. 13.4 - Describe in words the strings in each of these...Ch. 13.4 - Prob. 2ECh. 13.4 - Prob. 3ECh. 13.4 - Prob. 4ECh. 13.4 - Express each of these sets using a regular...Ch. 13.4 - Express each of these sets using a regular...Ch. 13.4 - Express each of these sets using a regular...Ch. 13.4 - Construct deterministic finite-state automata that...Ch. 13.4 - Construct nondeterministic finite-state automata...Ch. 13.4 - Construct nondeterministic finite-state automata...Ch. 13.4 - Show that if A is a regular set, then AR, the set...Ch. 13.4 - Using the construction described in the proof of...Ch. 13.4 - Using the construction described in the proof of...Ch. 13.4 - Construct a nondeterministic finite-state...Ch. 13.4 - In Exercises 15-17 conflict a regular grammar...Ch. 13.4 - In Exercises 15-17 conflict a regular grammar...Ch. 13.4 - In Exercises 15-17 conflict a regular grammar...Ch. 13.4 - Show that the finite-state automaton constructed...Ch. 13.4 - Show that the regular grammar constructed from a...Ch. 13.4 - Show that every nondeterministic finite-state...Ch. 13.4 - Let M=(S,I,f,s0,F) be a deterministic finite-state...Ch. 13.4 - One important technique used to prove that certain...Ch. 13.4 - Show that the set 02n1nn=0,1,2,... is not regular...Ch. 13.4 - Show that the set {1n2n=0,1,2,...} is not regular...Ch. 13.4 - Show that the set of palindromes over {0, 1} is...Ch. 13.4 - Prob. 26ECh. 13.4 - Prob. 27ECh. 13.4 - Prob. 28ECh. 13.4 - Prob. 29ECh. 13.4 - Prob. 30ECh. 13.4 - Use Exercise 29 to show that the language...Ch. 13.5 - Let T be the Turing machine defined by the...Ch. 13.5 - Let T be the Turing machine defined by the...Ch. 13.5 - What does the Turing machine defined by the...Ch. 13.5 - What does the Turing machine described by the...Ch. 13.5 - What does the Turing machine described by the...Ch. 13.5 - Construct a Turing machine with tape 0, 1, and B...Ch. 13.5 - Construct a Turning machine with tape symbols 0,...Ch. 13.5 - Construct a Turing machine with tape symbols 0, 1,...Ch. 13.5 - Construct a Turing machine with tape symbols 0, 1,...Ch. 13.5 - Construct a Turing machine with tape symbols 0, 1,...Ch. 13.5 - Construct a Turing machine that recognizes the set...Ch. 13.5 - Construct a Turing machine that recognizes the set...Ch. 13.5 - Construct a Turing machine that recognizes the set...Ch. 13.5 - Show at each step the contents of the tape of the...Ch. 13.5 - Explain why the Turing machine in Example 3...Ch. 13.5 - Construct a Turing machine that recognizes the set...Ch. 13.5 - Construct a Turing machine that recognizes the set...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turning machine that computes the...Ch. 13.5 - Prob. 27ECh. 13.5 - Prob. 28ECh. 13.5 - Which of the following problems is a decision...Ch. 13.5 - Which of the following problems is a decision...Ch. 13.5 - Prob. 31ECh. 13.5 - Show that the function B(n) cannot be computed by...Ch. 13 - a) Define a phrase-structure grammar. b) What does...Ch. 13 - a) What is the language generated by a...Ch. 13 - Prob. 3RQCh. 13 - Prob. 4RQCh. 13 - Prob. 5RQCh. 13 - a) What is a finite-state machine? b) Show how a...Ch. 13 - Prob. 7RQCh. 13 - Prob. 8RQCh. 13 - Prob. 9RQCh. 13 - Prob. 10RQCh. 13 - a) Define a nondeterministic finite-state...Ch. 13 - a) Define the set of regular expressions over a...Ch. 13 - Prob. 13RQCh. 13 - Prob. 14RQCh. 13 - Prob. 15RQCh. 13 - Prob. 16RQCh. 13 - Describe how Turing machines are used to recognize...Ch. 13 - Prob. 18RQCh. 13 - Prob. 19RQCh. 13 - Prob. 1SECh. 13 - Prob. 2SECh. 13 - Prob. 3SECh. 13 - Prob. 4SECh. 13 - Prob. 5SECh. 13 - Prob. 6SECh. 13 - Prob. 7SECh. 13 - Prob. 8SECh. 13 - Prob. 9SECh. 13 - Prob. 10SECh. 13 - Prob. 11SECh. 13 - Prob. 12SECh. 13 - Prob. 13SECh. 13 - Construct a finite-state machine with output that...Ch. 13 - Construct a finite-state machine with output that...Ch. 13 - Prob. 16SECh. 13 - Prob. 17SECh. 13 - Prob. 18SECh. 13 - Construct a deterministic finite-state automaton...Ch. 13 - Prob. 20SECh. 13 - Prob. 21SECh. 13 - Prob. 22SECh. 13 - Prob. 23SECh. 13 - Prob. 24SECh. 13 - Prob. 25SECh. 13 - Show that {02nnN} is not regular. You may use the...Ch. 13 - Prob. 27SECh. 13 - Prob. 28SECh. 13 - Construct a Turing machine that computes the...Ch. 13 - Prob. 30SECh. 13 - Prob. 1CPCh. 13 - Prob. 2CPCh. 13 - Prob. 3CPCh. 13 - Prob. 4CPCh. 13 - Given the state table of a Moore machine and an...Ch. 13 - Given the state table of a Mealy machine and an...Ch. 13 - Given the state table of a deterministic...Ch. 13 - Prob. 8CPCh. 13 - Prob. 9CPCh. 13 - Prob. 10CPCh. 13 - Given a regular grammar, construct a finite-state...Ch. 13 - Given a finite-state automaton, construct a...Ch. 13 - Prob. 13CPCh. 13 - Solve the busy beaver problem for two states by...Ch. 13 - Prob. 2CAECh. 13 - Prob. 3CAECh. 13 - Prob. 4CAECh. 13 - Prob. 5CAECh. 13 - Prob. 1WPCh. 13 - Describe the Backus-Naur form (and extended...Ch. 13 - Explain how finite-state machines are used by...Ch. 13 - Explain how finite-state machines are used in the...Ch. 13 - Explain how finite-state machines are used in...Ch. 13 - Compare the use of Moore machines versus Mealy...Ch. 13 - Explain the concept of minimizing finite-state...Ch. 13 - Give the definition of cellular automata, Explain...Ch. 13 - Define a pushdown automaton. Explain how pushdown...Ch. 13 - Define a linear-bounded automaton. Explain how...Ch. 13 - Prob. 11WPCh. 13 - Prob. 12WPCh. 13 - Prob. 13WPCh. 13 - Show that a Turing machine can simulate any action...Ch. 13 - Prob. 15WPCh. 13 - Describe the basic concepts of the lambda-calculus...Ch. 13 - Show that a Turing machine as defined in this...Ch. 13 - Prob. 18WP
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.Similar questions
- (1) Find a grammar that generates language L = {b" :n >0 }. (2) Find a grammar that generates language L = {b"a" : m,n 2 0}. (3) Find a grammar that generates language L = {b"a" : m > n, n20}.arrow_forward2. Answer each part for the following context-free grammar. R→ XRX | S S-> aTb | bТа T→ XTX|X | € X→ a | b a. What are the variables and terminals of G? Which is the start symbol? b. Give three examples of strings in L(G). c. Give three examples of strings not in L(G).arrow_forwardTransform the grammar with productions S→abAB A→aAB/∊ B→bbA into Chomsky normal formarrow_forward
- ALEKS - Christian Seither - Learn X + ● https://www-awu.aleks.com/alekscgi/x/Isl.exe/10_u-IgNslkr7j8P3jH-1BjnuwZGiweF Here are the meanings of some of the symbols that appear in the statements belo means "is a subset of." C means "is a proper subset of." Z means "is not a subset of." Øis the empty set. For each statement, decide if it is true or false. . SETS Identifying true statements involving subsets and proper subsets Statement (11, 13, 15) Jxplanation Check (11, 12, 13, 14, 15} (7,9) Ø (c. d. f. g} = (d, f} (q, r, w) C (q, r, w} True False O 0 O O O Search X hparrow_forward5. Using the following context free grammar give a parse tree for the strings. E → E +T|T T → TxF|F F → (E)\a (a) a+a+a (b) ((a))arrow_forward3. Consider the following CFG S → SS+ | SS* | a Check whether the grammar is ambiguous. If so, eliminate the ambiguity in the grammat.arrow_forward
- Let A = {a, b, c, d, e, f}, and let G and H be the following equivalence %3| relations in A: G = IAU{(a,b), (b, a) , (b, c) , (c, b) , (a, c) , (c, a) , (d, e), (e, d)} , H = IAU{(b, c) , (c, b)} . %3D Clearly, H is a refinement of G. Exhibit the sets A/G, A/H, G/H, (A/H)/(G/H).arrow_forwardRoster form: C = { Sunday, Monday, Tuesday, Wednesday,Thursday, Friday, Saturday } What is the Set Builder form?arrow_forward6. Give a recursive definition of each of these sets of ordered pairs of positive integers. PS:Please help me by doing all the subparts as it is connected correctly on a word processing document.arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
Discrete Mathematics and Its Applications ( 8th I...MathISBN:9781259676512Author:Kenneth H RosenPublisher:McGraw-Hill Education
Mathematics for Elementary Teachers with Activiti...MathISBN:9780134392790Author:Beckmann, SybillaPublisher:PEARSON
Thinking Mathematically (7th Edition)MathISBN:9780134683713Author:Robert F. BlitzerPublisher:PEARSON
Discrete Mathematics With ApplicationsMathISBN:9781337694193Author:EPP, Susanna S.Publisher:Cengage Learning,
Pathways To Math Literacy (looseleaf)MathISBN:9781259985607Author:David Sobecki Professor, Brian A. MercerPublisher:McGraw-Hill Education
Discrete Mathematics and Its Applications ( 8th I...
Math
ISBN:9781259676512
Author:Kenneth H Rosen
Publisher:McGraw-Hill Education
Mathematics for Elementary Teachers with Activiti...
Math
ISBN:9780134392790
Author:Beckmann, Sybilla
Publisher:PEARSON
Thinking Mathematically (7th Edition)
Math
ISBN:9780134683713
Author:Robert F. Blitzer
Publisher:PEARSON
Discrete Mathematics With Applications
Math
ISBN:9781337694193
Author:EPP, Susanna S.
Publisher:Cengage Learning,
Pathways To Math Literacy (looseleaf)
Math
ISBN:9781259985607
Author:David Sobecki Professor, Brian A. Mercer
Publisher:McGraw-Hill Education
Finite State Machine (Finite Automata); Author: Neso Academy;https://www.youtube.com/watch?v=Qa6csfkK7_I;License: Standard YouTube License, CC-BY
Finite State Machine (Prerequisites); Author: Neso Academy;https://www.youtube.com/watch?v=TpIBUeyOuv8;License: Standard YouTube License, CC-BY