Find context-free grammars generating

Assignment Help Theory of Computation

Reference no: EM132500501

Question 1. Find context-free grammars generating the following languages, and justify that they generate them:

(a) L1 = {aⁱb^jc^k | i = j or j = k}.

(b) L2 = {aⁱb^jc^k | i ≠ j + k }

Question 2. Prove that the CFG G with productions S → 0S1S | 1S0S | Λ generates the language L = {x ∈ {0, 1}∗ | n0(x) = n1(x)}.

Question 3. Show that if L is accepted by a PDA in which no move replaces the top stack symbol with Λ, then L is regular.

Question 4. Suppose that M is a PDA accepting L. Describe how to construct a PDA accepting the language L∗ and justify that it does accept L∗. (Remember that the stack may become empty when M accepts a string!)

Question 5. Show that if there is a PDA M = (Q, Σ, Γ, q0, Z0, A, δ) accepting language L by empty stack (i.e. x ∈ L if and only if (q0, x, Z0) €∗M (q, Λ, Λ) for some state q ∈ Q), then there is a PDA M1 = (Q1, Σ, Γ1, q1, Z1, A1, δ1) accepting L by final state (i.e. x ∈ L if and only if (q1, x, Z1) €∗M1 (q, Λ, α) for some α ∈ Γ∗1 and q ∈ A1).

Attachment:- Homework Assignment.rar

Reference no: EM132500501

Questions Cloud

Find what was the cost of goods sold for september : Find What was the cost of goods sold for September. In September, Lauren Ashley Company purchased materials costing $240,000 and incurred direct

Identify the fixed and step and variable costs : What is the cost incurred by the campus for 150 people over a 1-week period? Desert Vista Homeless Campus provides shelter and breakfast to individuals.

Compare the competitive outcome with the cartel outcome : Compare the competitive outcome with the cartel outcome. What is the individual firm's incentive to cheat on the cartel? (show the procedure you reach your conc

BUS5WB - Data Warehousing and Big Data Assignment : BUS5WB - Data Warehousing and Big Data Assignment Help and Solution - La Trobe University Australia. Title- Smart City Design - Data Warehousing and 5G Networks

Find context-free grammars generating : Find context-free grammars generating the following languages, and justify that they generate and Describe how to construct a PDA accepting the language L

What are the variable costs and contribution margin : What are the variable costs, fixed costs, and contribution margin? Sales Commissions 280,000 Fixed Advertising Expenses 20,000 Variable Administrative Expenses.

What price will it set for fee : The only golf course in an isolatd town incurs a marginal cost of $5 per round of golf. It wishes to charge a membership fee and a fee per round of golf.

Determine the cournot equilibrium : There are only two firms, A and B, and each has a marginal cost of 2. Determine the Cournot equilibrium.

Providing a vital public service : Augustine has decided to build their own municipal water supply. They must now decide what price to charge consumers. After some careful research

User Account

All Pages