/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} 10E Give an informal description of ... [FREE SOLUTION] | 91Ó°ÊÓ

91Ó°ÊÓ

Log out

Learning Materials

Features

Discover

Chapter 2: 10E (page 155)

Give an informal description of a pushdown automaton that recognizes the language in Exercise 2.9.

Short Answer

Expert verified

Informal description of the pushdown automaton that recognizes the language can be given.

A={ajbjck|i=jorj=kwherei,j,k≥0}canbegiven

Step by step solution

01

Explain pushdown automaton

Pushdown Automaton write symbols on the stack and read them. Writing a new symbol pushes down all the symbols in the stack before.

02

Give an informal description of a pushdown automaton that recognizes the language A.

Informal description of the pushdown automaton that recognizes the language

A={ajbjck|i=jorj=kwherei,k≥0}isasfollows

  1. Nondeterministic, branching to step 2 or 6.
  2. Read and push a ’s.
  3. Pop a’s, and read b ’s.
  4. If stack is empty,accept.
  5. Skip a’s and c’s input.
  6. Push b’s
  7. Read c ’s.
  8. When stack is empty and c’s finish, accept.

Therefore, the informal description has been given

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91Ó°ÊÓ!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Recall the CFG G4 that we gave in Example 2.4. For convenience, let’s rename its variables with single letters as follows.
E→E+TTT→T×FFF→(E)a

Give parse trees and derivations for each string.

a. a

b. a+a

c. a+a+a

d. ((a))

Give an example of a language that is not context free but that acts like a CFL in the pumping lemma. Prove that your example works. (See the analogous example for regular languages in Problem 1.54.)

Let G=(V,Σ,R,⟨STMT⟩)be the following grammar.

⟨STMT⟩→⟨ASSIGN⟩|⟨IF-THEN⟩|⟨IF-THEN-ELSE⟩⟨IF-THEN⟩→ifconditionthen⟨STMT⟩⟨IF-THEN-ELSE⟩→ifconditionthen⟨STMT⟩else⟨STMT⟩⟨ASSIGN⟩→a:=1

Σ={if,condition,then,else,a:=1}V={⟨STMT⟩,⟨IF-THEN⟩,⟨IF-THEN-ELSE⟩,⟨ASSIGN⟩}

G is a natural-looking grammar for a fragment of a programming language, but G is ambiguous.

a. Show that G is ambiguous.

b. Give a new unambiguous grammar for the same language

Answer each part for the following context-free grammar G

R→XRX|SS→aTb|bTaT→XTX|X|εX→a|b

  1. What are the variables of G?
  2. What are the terminals of G?
  3. Which is the start variable of G?
  4. Give three strings in L(G).
  5. Give three strings not inL(G) .
  6. True or False: T⇒aba.
  7. True or False: T⇒∗aba.
  8. True or False:T⇒T .
  9. True or False: T⇒∗T.
  10. True or False:XXX⇒∗aba .
  11. True or False: X⇒∗aba
  12. True or False:role="math" localid="1660812124187" T⇒∗XX.
  13. True or False: T⇒∗XXX.
  14. True or False: S⇒∗ε.
  15. Give a description in English of L(G) .

Give informal descriptions and state diagrams of pushdown automata for the languages in Exercise 2.4
See all solutions

Recommended explanations on Computer Science Textbooks

Fintech

Read Explanation

Databases

Read Explanation

Computer Programming

Read Explanation

Cloud Services

Read Explanation

Computer Network

Read Explanation

Cybersecurity in Computer Science

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.