Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Show that the finite-state automaton constructed from a regular grammar in the proof of Theorem 2 recognizes the set generated by this grammar.

Short Answer

Expert verified

The finite-state automaton produced from a regular grammar in the proof of Theorem 2 recognizes the set created by this grammar is proved as true.

Step by step solution

Achieve better grades quicker with Premium

  • Unlimited AI interaction
  • Study offline
  • Say goodbye to ads
  • Export flashcards

Over 22 million students worldwide already upgrade their learning with Vaia!

01

General form

Finite-state automaton (Definition):A finite-state automaton \({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\) consists of an initial or start state \({{\bf{s}}_0}\), a finite set S of states, a finite alphabet of inputs I, a transition function f that assigns a subsequent state to each pair of states and inputs (such that \({\bf{f:S \times I}} \to {\bf{S}}\)), and a subset F of S made up of final states (or accepting states).

Regular expressions (Definition):A recursive definition of the regular expressions over a set I is as follows:

A regular expression with the symbol \(\emptyset \);

A regular expression with the symbol \({\bf{\lambda }}\);

whenever \({\bf{x}} \in {\bf{I}}\); the symbol x is a regular expression.

When A and B are regular expressions, the symbols \(\left( {{\bf{AB}}} \right){\bf{,}}\left( {{\bf{A}} \cup {\bf{B}}} \right){\bf{,}}\) and \({\bf{A*}}\) are also regular expressions.

Regular sets are the sets that regular expressions represent.

Theorem 2: A set is formed by a regular grammar if and only if it is a regular set.

Rules of regular expression represents a set:

\(\emptyset \) represents the string-free set, or the empty set;

\({\bf{\lambda }}\) represents the set \(\left\{ {\bf{\lambda }} \right\}\), which is the set containing the empty string;

The string having the symbol x in it is represented by the set \(\left\{ {\bf{x}} \right\}\);

(AB)depicts the order of the sets that are represented by bothAand B;

The combination of the sets that bothA andBrepresent is represented by \(\left( {{\bf{A}} \cup {\bf{B}}} \right)\);

The Kleene closure of the sets that Arepresents is represented by \({\bf{A*}}\).

02

Step 2: Proof of the given statement

Given that, the proof of Theorem 2.

To prove: The set produced by this grammar is recognised by the finite-state automaton created from a regular grammar.

Proof:

There is a distinct derivation for each terminal string in the grammar, and this is mirrored in how the machine functions (as each regular sub-expression has a unique machine that was given in the proof).

Additionally, those generated nonempty strings will be carefully guided to the machine's finished state.

The start state is turned into a final state, and the empty string will only be recognised if it is also included in the language. With the exception of \({\bf{1*}}\), which has the empty string \({\bf{\lambda }}\) as its final state, none of the other submachines mentioned in the proof have the start state as a final state.

Hence, the statement is proved as true.

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

Determine whether 1011 belongs to each of these regular sets.

  1. \({\bf{1}}0{\bf{*}}1{\bf{*}}\)
  2. \(0{\bf{*}}\left( {10 \cup 11} \right){\bf{*}}\)
  3. \(1\left( {01} \right){\bf{*1*}}\)
  4. \(1{\bf{*}}01\left( {0 \cup 1} \right)\)
  5. \(\left( {10} \right){\bf{*}}\left( {11} \right){\bf{*}}\)
  6. \(1\left( {00} \right){\bf{*}}\left( {{\bf{11}}} \right){\bf{*}}\)
  7. \(\left( {10} \right){\bf{*}}10{\bf{1}}1\)
  8. \(\left( {1 \cup 00} \right)\left( {01 \cup 0} \right)1{\bf{*}}\)

Let G be the grammar with V = {a, b, c, S}; T = {a, b, c}; starting symbol S; and productions \({\bf{S }} \to {\bf{ abS, S }} \to {\bf{ bcS, S }} \to {\bf{ bbS, S }} \to {\bf{ a, and S }} \to {\bf{ cb}}{\bf{.}}\)Construct derivation trees for

\(\begin{array}{*{20}{l}}{{\bf{a) bcbba}}{\bf{.}}}\\{{\bf{b) bbbcbba}}{\bf{.}}}\\{{\bf{c) bcabbbbbcb}}{\bf{.}}}\end{array}\)

Let V = {S, A, B, a, b} and T = {a, b}. Find the language generated by the grammar (V, T, S, P) when theset P of productions consists of

\(\begin{array}{*{20}{l}}{{\bf{a) S }} \to {\bf{ AB, A }} \to {\bf{ ab, B }} \to {\bf{ bb}}{\bf{.}}}\\{{\bf{b) S }} \to {\bf{ AB, S }} \to {\bf{ aA, A }} \to {\bf{ a, B }} \to {\bf{ ba}}{\bf{.}}}\\{{\bf{c) S }} \to {\bf{ AB, S }} \to {\bf{ AA, A }} \to {\bf{ aB, A }} \to {\bf{ ab, B }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{d) S }} \to {\bf{ AA, S }} \to {\bf{ B, A }} \to {\bf{ aaA, A }} \to {\bf{ aa, B }} \to {\bf{ bB, B }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{e) S }} \to {\bf{ AB, A }} \to {\bf{ aAb, B }} \to {\bf{ bBa, A }} \to {\bf{ \lambda , B }} \to {\bf{ \lambda }}{\bf{.}}}\end{array}\)

In Exercises 16โ€“22 find the language recognized by the given deterministic finite-state automaton

Let G = (V, T, S, P) be the phrase-structure grammar with V = {0, 1, A, S}, T = {0, 1}, and set of productions P consisting of S โ†’ 1S, S โ†’ 00A, A โ†’ 0A, and A โ†’ 0.

a) Show that 111000 belongs to the language generated by G.

b) Show that 11001 does not belong to the language generated by G.

c) What is the language generated by G?

See all solutions

Recommended explanations on Math Textbooks

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.

Sign-up for free