DEFINITION 2.8A context-free grammar is in Chomsky normal form if every rule isof the formA → BCA → awhere a is any terminal and A, B, and C are any variables-exceptthat B and C may not be the start variable. In addition, we permitthe rule Se, where S is the start variable.ExampleSASA aBA BSB→ beSo → SS → ASA | aBABISB → beSo SSASA | aBa|SA|AS| SABSB-bSo ASA| aBa|SA| ASSASA aBa|SA| ASABS bB-bSo SSASA aB aABSCB-beA₁So SASA | aBa|SA| ASSASA aBa|SA| ASA → B|SB-bSo ASA aBa|SA| ASSASA aBa| SA ASA → Sb ASA | aBa|SA| ASB-bSo AA₁ |UB|a|SA| ASSAA₁ |UB|a|SA| ASAb AA₁ |UB|a|SA| ASSAU → aB→ bSo SSASA | aBa|SA|AS| SA → B SeB-b 2. Convert the following CFG into an equivalent CFG in Chomsky normal form, usingthe procedure given in Theorem 2.9.A → BAB | B &B → 00 | E

A non-terminal generating a terminal. Example: A -> aA non-terminal generating two non-terminal.…

Answered: 2. Convert the following CFG into an…

2. Convert the following CFG into an equivalent CFG in Chomsky normal form, using the procedure given in Theorem 2.9. A → BAB | B& B → 00 | E

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Q: Determine all the essential prime implicants. с) d) not determine the additional prime implicants…

A: Truth table is given. WE need to determine the Essential prime implicants and prime implicant and…

Q: 1. Convert the following CFG into Chomsky Normal Form (CNF): S → AbA A → Aa |ε

A: Introduction : CFG stands for Context-Free Grammar, and CNF stands for Chomsky Normal Form.…

Q: Differential Equations by Laplace transforms ▪ On this activity, you will learn to solve initial…

A: clc; clear; close all; %clears all variables in current workspace syms y(t), t; Dy = diff(y); D2y =…

Q: b. Apply DeMorgan's theorem to the following logical function: F = AB + CD

A: Answer: This question based on logical reasoning. I have answered in written format.

Q: Assume an MIP with five integer variables, X1, X2, X3, X4, and x5. Given the following LP relaxation…

A: The question presents a Mixed Integer Programming (MIP) problem with five integer variables x1, x2,…

Q: For problems 4-7, use "left-to-right concatenation from A to Z" as we did in class to convert the…

A: 4. b[ac]*c CFG for b[ac]*c: This can be written as ba*c | bc*c S -> bABc A -> (empty) | Aa B…

Q: Simplify the following Boolean function F, together with the don't-care conditions d, and then…

Q: Let f : B 3 → B where f(x, y, z) = (x + z)y. (a) Provide a truth table for the function. (b) Derive…

A: In Boolean algebra, the canonical disjunctive normal form (DNF) and canonical conjunctive normal…

Q: Solve the fou ring 1. Write an M-function function [x,iter,err]-Jacobi(A,b,tol,kmax) Then, test it…

A: 1function [x, iter, err] = Jacobi(A, b, tol, kmax) 2 n = length(b); 3 x = zeros(n, 1); 4…

Q: Simplify the equation to a)sum of product b)product of sum F=(x, y, z)=Σ(0,1,4,5,6);d(2,3,7)

A: We are given a Boolean function and we are going to find out its SOP (sum of product) and…

Q: Boolean Algebra Simplify the following functions to a minimum number of literals. Show step-by-step…

A: We need to find the simplified form of the functions: A'.C' + A.B.C + A.C' & need to draw…

Q: b. State the Cook-Levin Theorem.

A: Note: There are multiple questions are given in one question. According to the rule, you will get…

Q: Problem 3 Determine the root/s of the following graphically: (Using Matlab/Python) a. f(x) = x³ +…

A: a. To find the roots of f(x) = x^3 + 3x^2 - 9 graphically: Define the function f(x) = x^3 + 3x^2 -…

Q: F(A,B,C)=A'B'+ABC'

A: De Morgan's Theorem is a fundamental concept in Boolean algebra that provides a way to simplify…

Q: (a) Examine and simplify the following function using Karnaugh maps: F(w,x, y, z) = ) m (1,4,7,12,9)…

A: Answer for the both questions is given below.

Q: 5. Determine the range of K for stability of the following characteristic equation, (c) s(s2 + s+…

Q: Problem 1. Using Karnaugh maps find a minimal sum of products expression and a minimal product of…

A: POS form-POS produces a logical expression comprised of the AND of the multiple OR terms SOP…

Q: Bayes Theorem.

A: Summary Bayes’ theorem describes the possibility of an event occurring on the subject of a given…

Q: For the function f(a,b,c,d)=Em(0,1,3,5, 6,7,8,10,14,15), find all minimum sum-of-products solution,…

A: Consider the function, f(a,b,c,d) = ∑m(0,1,3,5,6,7,8,10,14,15) Step 1: To begin, we must group all…

Q: 1. Complete the implicant table to find all the prime implicants for the given minterm expansion…

A: A prime implicant of a function is an implicant that cannot be covered by a more general implicant.…

Q: 8. Write the following equation in reduced POS form: F(w,x,y,z) = [I(4, 11, 15) + Md(1,2,3,7, 12

A: Truth Table w x y z O/P 0 0 0 0 1 0 0 0 1 x 0 0 1 0 x 0 0 1 1 x 0 1 0 0 0 0 1…

Q: 'B'C + A'BC' AB'C B+ AC - A'B'C

Q: Problem 1 • Determine if the following equation is valid X₁ X3 + X₂X3+X₁X₂ = X1X2 +X1X3+X₂X3 • Let's…

A: In Canonical SOP, each product term contains all literals. Given equation: x1'x3'+x2x3+x1x2' =…

Q: 5. Using the following Truth Table, (a) Find out the maxterm expansion for the function F A В C F 1…

A: 5. Un Maxterm we look for function where the output results in 0. So, F=π(0,4,5,6) Maxterm expansion…

Q: Using Kmaps, determine all the minimal sums and minimal products for the following functions:…

A: According to bartleby guidelines we are supposed to answer only 1 question so I have answered…

Q: Simplification: Determine the simplified equation of the following. 1. F= XZ +XY+ YZ 2. F= AB + ACD…

A: 1. F= XZ+X'Y'+YZ 2. F= AB + ACD + B'D + B'D And third one is circuit diagram

Q: Problem 2. Given a sum of products or product of sums expression for F, it is possible to fill in…

A: take those terms and put there 0 and 1 as per values given in the kmap

Q: Chapter 3, problem 2: expressions: d) f(a,b,c,d) = For each of the following, find all minimum sum…

A: The given function is : f(a, b, c, d) = Σm(1, 2, 3, 5, 6, 7, 8, 11, 13, 15)

Q: (2 pts. each) (a) List the minterms of the function. (b) List the minterms of F'. (c) Express Fin…

A: A) min terms of the function are Product term which contains each of the n variables in either…

Q: Problem 5. 1+x In 1-x What is the Maclaurin's series for In(1-x), and what is the series for

A: Answer: 1

Q: Rewrite the given f(x) to avoid loss of significance by using the first two non zero terms in…

A: To rewrite the function f(x) = (sin(x)/x) - cos(x) using the first two non-zero terms in the Taylor…

Q: Karnaugh Map to simplify the following logic functions F=(1,2,3,8,9, 11, 14). D(0,4,6,10,12) F=(2,…

A: (i) I have drawn the KMAP, solved it and attached Truth table and Circuit Diagram for better…

Q: Question 2: Use a Karnaugh map to simplify the Boolean function and find the SOP and POS for each…

A: Given Boolean functions are, F(A,B,C,D)=ΣM(1,3,7,11,15) F(A,B,C,D)=ΣM(0,2,5)…

Q: Convert the following CFG into an equivalent CFG in Chomsky normal form, using the procedure given…

A: Convert the following cfg into equivalent CFG in cnf form: See below steps.

Question

DEFINITION 2.8
A context-free grammar is in Chomsky normal form if every rule is
of the form
A → BC
A → a
where a is any terminal and A, B, and C are any variables-except
that B and C may not be the start variable. In addition, we permit
the rule Se, where S is the start variable.
Example
SASA aB
A BS
B→ be
So → S
S → ASA | aB
ABIS
B → be
So S
SASA | aBa|SA|AS| S
ABS
B-b
So ASA| aBa|SA| AS
SASA aBa|SA| AS
ABS b
B-b
So S
SASA aB a
ABSC
B-be
A₁
So SASA | aBa|SA| AS
SASA aBa|SA| AS
A → B|S
B-b
So ASA aBa|SA| AS
SASA aBa| SA AS
A → Sb ASA | aBa|SA| AS
B-b
So AA₁ |UB|a|SA| AS
SAA₁ |UB|a|SA| AS
Ab AA₁ |UB|a|SA| AS
SA
U → a
B→ b
So S
SASA | aBa|SA|AS| S
A → B Se
B-b

2. Convert the following CFG into an equivalent CFG in Chomsky normal form, using
the procedure given in Theorem 2.9.
A → BAB | B &
B → 00 | E

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1: Rules for Chomsky Normal Form (CNF) :

VIEW

Step 2: 2. Convert the following CFG into an equivalent CFG in Chomsky normal form.

VIEW

Solution

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 3 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Fundamentals of Boolean Algebra and Digital Logics

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

simplify the equation using the de Morgan's Theorem
Please explain to me how to solve each one step by step
3) Simplify the following Boolean functions, using K-Inaps. F(w, x, y, z) = (1, 3, 4, 5, 6, 7, 9, 11, 13, 15) (4 pts) 1
Answer the following questions: a. Apply DeMorgan's Theorems to the following expression F = (ABC + DEF)' b. Apply DeMorgan's Theorems to the following expression F = ((A+B+C). D)' c. Use DeMorgan's Theorem in algebraic form to Prove F = A' + B' (A. B)' d. Use DeMorgan's Theorem in algebraic form to Prove F = A'. B' = (A + B)' e. Minimize the following Logic Expressions F, Y Algebraically and PROVE the function F to be equal to A'.C' + B, and the function Y to be equal to A+BC. A'.B'.C + A'.B.C'+A'.B.C+A.B.C'+A.B.C F (A, B, C) Y (A, B, C) (A+B) (A+C)
Use MATLAB to: (a) Approximate the roots of the function f (x) defined by: f(x) = x² sin(x) (b) Calculate the roots of f (x) as defined in part (a) in a span of [-6, 6]. (c) Estimate a function g(x) by deriving the Taylor series of the function (x) up to order 8. (d) Calculate the roots of the Taylor series in the span of [-6, 6].
QUESTION 3 a) Derive the Boolean expression of M in standard Product of Sums (POS) and Sum of Product (SOP) format for the given truth table. Input Output M А в с 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 b) Apply K-map to minimize the Boolean Expression M in SOP form.
Please use Matlab
Question 1 a) State the advantages of applying Karnaugh map instead of Boolean Laws to simplify a function. b) Let's say your ULAB student ID is 173014009. So, from the available distinct digits in the student ID, a function F can be expressed as F = E(0, 1,3,4,7,9). Now, express the following function F into a simplified Product-of-Sum (POS) form. Show step-by-step process to express the function F. F = E(digits in your student ID)
5. Let f:X→Y and g:Y→Z be one-to-one correspondences. (a) Prove that g◦fmust be a one-to-one correspondence. (b) Prove that (g◦f)−1=f−1◦g−1.
Problem # 16 Compute inverses of 6, 7,8 a) in the multiplicative group Z',, b) in the multiplicative group Z',
Using MATLAB functions poly and polyder, compute the relative condition numbers of the roots 1, 2, ..., 20 of the Wilkinson polynomial 20 w(x) = (x1)(x-2)(x - 20) = x²0 210x¹⁹+... 19 with respect to perturbation of the coefficient of 2x¹⁹, a19, from -210 to -210+2-23 Present your results in a tabular form and write your conclusion on the ill-conditioninig of the Wilkinson polynomial. (Recall: condition number for the jth root is kj |a₁x²=1| \w'(x₂)
By using Truth Table, show that (p→q)→r and (p→r)→q are not logically equivalent