Suggested languages for you:

Americas

Europe

Problem 13

\\} ;\( and \)R$ is the set of rules: $$ \begin{aligned} &S \rightarrow T T \mid U \\ &T … # Let \(G=(V, \Sigma, R, S)\) be the following grammar. $V=\\{S, T, U\\} ; \Sigma=\\{0, \\#\\} ;\( and \)R$ is the set of rules: $$ \begin{aligned} &S \rightarrow T T \mid U \\ &T \rightarrow 0 T|T 0| \\ &U \rightarrow 0 U 00 \mid \\# \end{aligned} $$ a. Describe \(L(G)\) in English. b. Prove that \(L(G)\) is not regular.

Expert verified

The language \(L(G)\) contains strings that either have an even number of consecutive 0s or have half as many 0s on the left side of the symbol '\\#' as on the right side. The language \(L(G)\) is not regular, as applying the Pumping Lemma leads to a contradiction.

What do you think about this solution?

We value your feedback to improve our textbook solutions.

- Access over 3 million high quality textbook solutions
- Access our popular flashcard, quiz, mock-exam and notes features
- Access our smart AI features to upgrade your learning

Chapter 2

Show that the class of context-free languages is closed under the regular operations, union, concatenation, and star.

Chapter 2

Let \(E=\left\\{\mathrm{a}^{\mathrm{i}} \mathrm{b}^{j} \mid i \neq j\right.\) and \(\left.2 i \neq j\right\\} .\) Show that \(E\) is a context-free language.

Chapter 2

If we disallow \(\varepsilon\)-rules in CFGs, we can simplify the \(D K\)-test. In the simplified test, we only need to check that each of \(D K\) 's accept states has a single rule. Prove that a CFG without \(\varepsilon\)-rules passes the simplified \(D K\)-test iff it is a DCFG.

Chapter 2

Use the results of Exercise \(2.16\) to give another proof that every regular language is context free, by showing how to convert a regular expression directly to an equivalent context-free grammar.

Chapter 2

Let \(C=\left\\{w w^{\mathcal{R}} \mid w \in\\{0,1\\}^{*}\right\\} .\) Prove that \(C\) is not a DCFL. (Hint: Suppose that when some DPDA \(P\) is started in state \(q\) with symbol \(x\) on the top of its stack, \(P\) never pops its stack below \(x\), no matter what input string \(P\) reads from that point on. In that case, the contents of \(P\) 's stack at that point cannot affect its subsequent behavior, so \(P\) 's subsequent behavior can depend only on \(q\) and \(x\).)

The first learning app that truly has everything you need to ace your exams in one place.

- Flashcards & Quizzes
- AI Study Assistant
- Smart Note-Taking
- Mock-Exams
- Study Planner