{"id":42,"date":"2018-07-19T10:32:30","date_gmt":"2018-07-19T10:32:30","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=42"},"modified":"2018-07-19T10:32:39","modified_gmt":"2018-07-19T10:32:39","slug":"finite-automata-dfa","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/finite-automata-dfa\/","title":{"rendered":"Finite automata \u2013DFA"},"content":{"raw":"

The primary objective of this module is to define patterns using Deterministic Finite Automata (DFA) and Non-deterministic Finite automata (NFA). As a first step, this module also discusses the procedure to convert a regular expression to \u03b5-NFA.<\/p>\r\n \r\n\r\n4.1 Transition Diagram<\/strong>\r\n\r\n \r\n

A transition diagram is a stylized flowchart or a directed graph that depicts the actions that take place when a lexical analyser is called by the parser to get the next token. It has been already discussed in the modules 1 and 3. Lexical analyser and the syntax analyser works together to carry out the analysis phase of the compiler. The parser issues a \u201cgettoken\u201d command while a lexer \u201cgives\u201d a token to the parser. This token is given by matching a longest matching pattern, where the pattern is specified by the Finite Automata or Regular expression. Figure 4.1 shows simple automata for the pattern \u201c > =\u201d.<\/p>\r\n \r\n\r\n\"\"\r\n

In figure 4.1, there is a designated special state called start state which is numbered as \u201c0\u201d. The other states are \u201c1\u201d, \u201c2\u201d, and \u201c3\u201d. In these states, \u201c2\u201d and \u201c3\u201d have been indicated with a double circle, which indicates a final or accepting state. Any path that takes from the start state to the final state is considered as a valid path and the sequence of edges constituting these edges qualify for the strings of the automata. In figure 4.1, the valid strings are \u201c>=\u201d and \u201c>\u201d. For the string \u201c>\u201d, other values that follow \u201c>\u201d is ignored and a valid prefix is chosen. At state 2, the lexer returns, <relop, GE>, indicating that the lexeme is \u201c>=\u201d which is \u201cGreater than or Equal to\u201d (GE) and the corresponding token associated is \u201crelop\u201d, indicating \u201crel<\/strong>ational op<\/strong>erator\u201d. The diagram of figure 4.1 corresponds to a finite automata (FA) and can be stated formally as ({0, 1, 2, 3}, {>, <, =\u201d, \u03b4, 0, {2,3}), where the transition function is indicated in figure 4.1. Figure 4.2 specifies a FA for identifiers in the Pascal language, where \u201cletter\u201d indicates any alphabet from A-Z or a-z and \u201cdigit\u201d indicates any number between 0 and 9 and it returns the token \u201cidentifier\u201d and the actual string encountered as \u201clexeme\u201d.<\/p>\r\n\"\"\r\n\r\n4.1.1 Deterministic Finite Automata<\/strong>\r\n\r\n \r\n

As can be seen from figures 4.1 and 4.2 the automata are deterministic as there is at most one transition on an input symbol from every state. Formally stating, a FA, by default is a Deterministic one and a five tuple representation (Q, \u2211 , \u03b4, q0, F), q0 belongs to Q and F is a subset of Q, \u03b4 is a mapping from Q x \u2211 to Q. Every string has exactly one path and hence it is faster for string matching. In a DFA, no state has an e-transition that is the DFA cannot change state without consuming any input symbol. A DFA accepts an input string x if and only if there is some path in the transition graph from start state to some accepting state.<\/p>\r\n \r\n

Let us consider one more example. Let us construct a DFA M which can accept the strings which begin with \u2018a\u2019<\/em> or \u2018b\u2019<\/em>, or begin with \u2018c\u2019<\/em> and contain at most one \u2018a\u2019.<\/em><\/p>\r\n\"\"\r\n\r\n \r\n

Constructing the DFA involves, drawing the directed graph which is nothing but the transition diagram. The string can begin with a, b, c. Hence, have an edge, from state \u20180\u2019 on, a, b, c to final states 2, 1. If the string begins with b, c, then there is no restriction on the sequence of characters that follow. Hence, transition on a, b, c from state \u20181\u2019 can stay in state \u20181\u2019 itself. On the other hand, from state 2, there should be exactly one edge on \u2018a\u2019, while b, c from the states 2, 3, can stay there itself. For this representation, a regular expression would be easier to write. The regular expression corresponding to this is given below<\/p>\r\n \r\n\r\n\r\n\r\n
(a+b)(a+b+c)* + c(b+c)*a(b+c)*<\/td>\r\n(4.1)<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n

However, for string matching and a better understanding, a graphical representation of the automata is preferred. Hence, we convert one representation to the other. The details would be discussed in subsequent sections after the discussion of NFA and \u03b5-NFA.<\/p>\r\n \r\n\r\n4.1.2 Non-deterministic finite Automata<\/strong>\r\n\r\n \r\n

The Non-deterministic finite automaton (NFA) is similar to deterministic finite automata but it gives more flexibility. It is a five tuple representation (Q, \u2211 , \u03b4, q0, F), q0 belongs to Q and F is a subset of Q and \u03b4 is a mapping from Q x \u2211 to 2Q . An example NFA is given below:<\/p>\r\n \r\n\r\n\"\"\r\n

\r\n

From figure 4.4 it can be seen, that from state 0, there are two edges on the input \u2018a\u2019 and \u2018b\u2019. Hence, to check whether a string that begins with \u201ca\u201d belongs to this NFA, multiple paths have to be verified and even if anyone path includes final state, it can be understood that the string belongs to the automata. Due to the necessity to check multiple possible paths, a NFA is slower in string matching.<\/p>\r\n \r\n

In an NFA, there can be more than one transition defined from a single state for an input symbol. However, in a DFA there can be at most one transition from a single state on an input symbol.<\/p>\r\n\r\n<\/div>\r\n \r\n\r\n4.1.3<\/strong>\u00a0\u00a0\u00a0\u00a0 Non-Deterministic Finite automata with <\/strong>\u03b5\r\n\r\n \r\n

This representation is same as NFA but is still more flexible to change state without consuming any input symbol. The difference between this NFA and NFA without \u03f5, is that the transition function \u03b4 is a mapping from Q x \u2211 U {\u03b5} to 2Q<\/p>\r\n \r\n

Hence, to check whether a string belongs to this NFA, we need to find the \u03b5 -Closure(r) if r is a state reached in one of the paths. \u03f5<\/strong> -Closure(r) is defined as the set of states including \u2018r\u2019 that can be reached from state \u2018r\u2019 on \u03f5<\/strong> transitions only. Since, there is a necessity to compute \u03b5 -Closure, this automata is still slower than NFA for string matching. An example of a \u03b5 -NFA is given in Figure 4.5. From figure 4.5, it can be seen that from state 1 there is a transition on \u03f5. Furthermore it can be stated that \u03b5-Closure(1) = {1, 3, 2} and \u03b5-<\/strong>Closure(3) = {3, 2} as an example for \u03b5-Closure.<\/p>\r\n\"\"\r\n

\r\n\r\n4.2 Regular Expression and Finite Automata<\/strong>\r\n\r\n \r\n

A NFA accepts an input string \u2018x\u2019 if and only if there is some path in the transition graph from start state to some accepting state. A path can be represented by a sequence of state transitions called \u201cmoves\u201d. As already discussed in this module, for some patterns defining a regular expression is easier and for some other an automaton is easier to construct. However, depending on the application, one may prefer a regular expression or an automata. Hence, procedures need to be defined to convert one representation to the other. As we have already discussed, a DFA is quicker for string matching and so is a regular expression. On the other hand, constructing a DFA or regular expression is difficult while constructing a NFA or \u03b5-NFA is easier.<\/p>\r\n \r\n

An application would prefer a DFA for its representation while the input could be available as a regular expression. A regular expression could be converted to a DFA using any one of the following procedures<\/p>\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>Convert to an \u03b5-NFA, convert this to a NFA and convert the NFA to DFA using the subset construction algorithm\r\n\r\n<\/div>\r\n

    \r\n \t
  1. Convert to DFA based on the syntax tree procedure.<\/li>\r\n<\/ol>\r\n

    If the Thompson\u2019s subset construction algorithm as indicated in (1) is preferred, then the constructed DFA need to be minimized. However, the procedure followed by (2) gives a minimized DFA.<\/p>\r\n \r\n\r\n4.3 Algorithm to convert regular expression to \u03f5-NFA<\/strong>\r\n\r\n \r\n

    The algorithm is based on the assumption that for every regular expression \u2018r\u2019 there exists an automaton. The first consideration in constructing the automata from regular expression is in prioritizing the operators. Kleene Closure operator \u201c*\u201d has the highest precedence followed by the concatenation operator \u201c.\u201d followed by the union operator \u201c+\u201d or \u201c|\u201d.<\/p>\r\n \r\n

    Figures 4.6 a, b and c give the automata for the simple regular expression without involving any regular expression operators.<\/p>\r\n\"\"\r\n

    Figure 4.6 a, is an automata corresponding to the regular expression \u201ca\u201d. The regular expression \u201ca\u201d corresponds to only one string \u201ca\u201d. This is given as an automaton with two states and one edge labeled \u201ca\u201d that goes from start to final state. Figure 4.6 b is an automata corresponding to the regular expression \u201c\u03b5\u201d. The difference between figures 4.6 a and 4.6b is just that the edge is labeled \u2018\u03b5\u2019 instead of \u2018a\u2019. Figure 4.6c corresponds to automata for the \u03a6 string. There is no edge from the start to the final state and hence no path exists from start to the final state. Thus, this automaton doesn\u2019t accept any string. The constraint that is posed in the construction is that there is exactly one final state.<\/p>\r\n \r\n

    A regular expression is formed using the base expression as an alphabet and connecting them using regular expression operators. Base expression is what has been discussed in Figure 4.6 (a-c). A regular expression can be formed using anyone of the operators, +, ., * which indicates union, concatenation or kleene closure. If R1, R2 are base regular expressions, another regular expression could be formed in one of the following ways:<\/p>\r\n \r\n\r\n\r\n\r\n\r\n\r\n
    R3<\/td>\r\n= R1+R2<\/td>\r\n(4.2)<\/td>\r\n<\/tr>\r\n
    R4<\/td>\r\n= R1 . R2<\/td>\r\n(4.3)<\/td>\r\n<\/tr>\r\n
    R5<\/td>\r\n= R1*<\/td>\r\n(4.4)<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\nEquation (4.2) indicates a new regular expression R3 formed by performing union of two regular expressions. The construction of the \u03f5-NFA is given in figure 4.7\r\n\r\n\"\"\r\n
    \r\n

    Let M1 and M2 be the automata corresponding to R1 and R2 respectively. A new automaton with \u03b5 transitions is constructed by adding two new states, one start and one final state. \u03b5 transitions are defined from the new start state to the existing automata M1, M2\u2019s start state. \u03b5 transitions are also defined from the final states of M1 and M2 to the new final state. Thus, if a string belongs to the expression R1, then it follows the path through M1 by suffixing and prefixing the string with \u03b5. On the other hand if a string corresponds to regular expression R2, then it follows the path of M2. Thus this new NFA accepts strings belonging to R1 and R2,\u00a0which is the implication of the union operator. To construct automata for other expressions, a-NFA\u00a0\u00a0<\/span>Equation 4.3 indicates the concatenation operator, where regular expression R4 corresponds to the strings of R1 followed by R2. The corresponding automata <\/span>is given in figure 4.8<\/span><\/p>\r\n\r\n<\/div>\r\n\"\"\r\n\r\n\"\"\r\n\r\nSummary:<\/strong>\r\n\r\n \r\n

    This module discussed the concepts of DFA, NFA and \u03b5-NFA and their ways of defining patterns for string matching. However, conversion from regular expression to automata may be required, and this module focused on the first step in converting regular expression to \u03f5-NFA.<\/p>","rendered":"

    The primary objective of this module is to define patterns using Deterministic Finite Automata (DFA) and Non-deterministic Finite automata (NFA). As a first step, this module also discusses the procedure to convert a regular expression to \u03b5-NFA.<\/p>\n

     <\/p>\n

    4.1 Transition Diagram<\/strong><\/p>\n

     <\/p>\n

    A transition diagram is a stylized flowchart or a directed graph that depicts the actions that take place when a lexical analyser is called by the parser to get the next token. It has been already discussed in the modules 1 and 3. Lexical analyser and the syntax analyser works together to carry out the analysis phase of the compiler. The parser issues a \u201cgettoken\u201d command while a lexer \u201cgives\u201d a token to the parser. This token is given by matching a longest matching pattern, where the pattern is specified by the Finite Automata or Regular expression. Figure 4.1 shows simple automata for the pattern \u201c > =\u201d.<\/p>\n

     <\/p>\n

    \"\"<\/p>\n

    In figure 4.1, there is a designated special state called start state which is numbered as \u201c0\u201d. The other states are \u201c1\u201d, \u201c2\u201d, and \u201c3\u201d. In these states, \u201c2\u201d and \u201c3\u201d have been indicated with a double circle, which indicates a final or accepting state. Any path that takes from the start state to the final state is considered as a valid path and the sequence of edges constituting these edges qualify for the strings of the automata. In figure 4.1, the valid strings are \u201c>=\u201d and \u201c>\u201d. For the string \u201c>\u201d, other values that follow \u201c>\u201d is ignored and a valid prefix is chosen. At state 2, the lexer returns, <relop, GE>, indicating that the lexeme is \u201c>=\u201d which is \u201cGreater than or Equal to\u201d (GE) and the corresponding token associated is \u201crelop\u201d, indicating \u201crel<\/strong>ational op<\/strong>erator\u201d. The diagram of figure 4.1 corresponds to a finite automata (FA) and can be stated formally as ({0, 1, 2, 3}, {>, <, =\u201d, \u03b4, 0, {2,3}), where the transition function is indicated in figure 4.1. Figure 4.2 specifies a FA for identifiers in the Pascal language, where \u201cletter\u201d indicates any alphabet from A-Z or a-z and \u201cdigit\u201d indicates any number between 0 and 9 and it returns the token \u201cidentifier\u201d and the actual string encountered as \u201clexeme\u201d.<\/p>\n

    \"\"<\/p>\n

    4.1.1 Deterministic Finite Automata<\/strong><\/p>\n

     <\/p>\n

    As can be seen from figures 4.1 and 4.2 the automata are deterministic as there is at most one transition on an input symbol from every state. Formally stating, a FA, by default is a Deterministic one and a five tuple representation (Q, \u2211 , \u03b4, q0, F), q0 belongs to Q and F is a subset of Q, \u03b4 is a mapping from Q x \u2211 to Q. Every string has exactly one path and hence it is faster for string matching. In a DFA, no state has an e-transition that is the DFA cannot change state without consuming any input symbol. A DFA accepts an input string x if and only if there is some path in the transition graph from start state to some accepting state.<\/p>\n

     <\/p>\n

    Let us consider one more example. Let us construct a DFA M which can accept the strings which begin with \u2018a\u2019<\/em> or \u2018b\u2019<\/em>, or begin with \u2018c\u2019<\/em> and contain at most one \u2018a\u2019.<\/em><\/p>\n

    \"\"<\/p>\n

     <\/p>\n

    Constructing the DFA involves, drawing the directed graph which is nothing but the transition diagram. The string can begin with a, b, c. Hence, have an edge, from state \u20180\u2019 on, a, b, c to final states 2, 1. If the string begins with b, c, then there is no restriction on the sequence of characters that follow. Hence, transition on a, b, c from state \u20181\u2019 can stay in state \u20181\u2019 itself. On the other hand, from state 2, there should be exactly one edge on \u2018a\u2019, while b, c from the states 2, 3, can stay there itself. For this representation, a regular expression would be easier to write. The regular expression corresponding to this is given below<\/p>\n

     <\/p>\n\n\n\n
    (a+b)(a+b+c)* + c(b+c)*a(b+c)*<\/td>\n(4.1)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

     <\/p>\n

    However, for string matching and a better understanding, a graphical representation of the automata is preferred. Hence, we convert one representation to the other. The details would be discussed in subsequent sections after the discussion of NFA and \u03b5-NFA.<\/p>\n

     <\/p>\n

    4.1.2 Non-deterministic finite Automata<\/strong><\/p>\n

     <\/p>\n

    The Non-deterministic finite automaton (NFA) is similar to deterministic finite automata but it gives more flexibility. It is a five tuple representation (Q, \u2211 , \u03b4, q0, F), q0 belongs to Q and F is a subset of Q and \u03b4 is a mapping from Q x \u2211 to 2Q . An example NFA is given below:<\/p>\n

     <\/p>\n

    \"\"<\/p>\n

    \n

    From figure 4.4 it can be seen, that from state 0, there are two edges on the input \u2018a\u2019 and \u2018b\u2019. Hence, to check whether a string that begins with \u201ca\u201d belongs to this NFA, multiple paths have to be verified and even if anyone path includes final state, it can be understood that the string belongs to the automata. Due to the necessity to check multiple possible paths, a NFA is slower in string matching.<\/p>\n

     <\/p>\n

    In an NFA, there can be more than one transition defined from a single state for an input symbol. However, in a DFA there can be at most one transition from a single state on an input symbol.<\/p>\n<\/div>\n

     <\/p>\n

    4.1.3<\/strong>\u00a0\u00a0\u00a0\u00a0 Non-Deterministic Finite automata with <\/strong>\u03b5<\/p>\n

     <\/p>\n

    This representation is same as NFA but is still more flexible to change state without consuming any input symbol. The difference between this NFA and NFA without \u03f5, is that the transition function \u03b4 is a mapping from Q x \u2211 U {\u03b5} to 2Q<\/p>\n

     <\/p>\n

    Hence, to check whether a string belongs to this NFA, we need to find the \u03b5 -Closure(r) if r is a state reached in one of the paths. \u03f5<\/strong> -Closure(r) is defined as the set of states including \u2018r\u2019 that can be reached from state \u2018r\u2019 on \u03f5<\/strong> transitions only. Since, there is a necessity to compute \u03b5 -Closure, this automata is still slower than NFA for string matching. An example of a \u03b5 -NFA is given in Figure 4.5. From figure 4.5, it can be seen that from state 1 there is a transition on \u03f5. Furthermore it can be stated that \u03b5-Closure(1) = {1, 3, 2} and \u03b5–<\/strong>Closure(3) = {3, 2} as an example for \u03b5-Closure.<\/p>\n

    \"\"<\/p>\n

    \n

    4.2 Regular Expression and Finite Automata<\/strong><\/p>\n

     <\/p>\n

    A NFA accepts an input string \u2018x\u2019 if and only if there is some path in the transition graph from start state to some accepting state. A path can be represented by a sequence of state transitions called \u201cmoves\u201d. As already discussed in this module, for some patterns defining a regular expression is easier and for some other an automaton is easier to construct. However, depending on the application, one may prefer a regular expression or an automata. Hence, procedures need to be defined to convert one representation to the other. As we have already discussed, a DFA is quicker for string matching and so is a regular expression. On the other hand, constructing a DFA or regular expression is difficult while constructing a NFA or \u03b5-NFA is easier.<\/p>\n

     <\/p>\n

    An application would prefer a DFA for its representation while the input could be available as a regular expression. A regular expression could be converted to a DFA using any one of the following procedures<\/p>\n

     <\/p>\n

    1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>Convert to an \u03b5-NFA, convert this to a NFA and convert the NFA to DFA using the subset construction algorithm<\/p>\n<\/div>\n

      \n
    1. Convert to DFA based on the syntax tree procedure.<\/li>\n<\/ol>\n

      If the Thompson\u2019s subset construction algorithm as indicated in (1) is preferred, then the constructed DFA need to be minimized. However, the procedure followed by (2) gives a minimized DFA.<\/p>\n

       <\/p>\n

      4.3 Algorithm to convert regular expression to \u03f5-NFA<\/strong><\/p>\n

       <\/p>\n

      The algorithm is based on the assumption that for every regular expression \u2018r\u2019 there exists an automaton. The first consideration in constructing the automata from regular expression is in prioritizing the operators. Kleene Closure operator \u201c*\u201d has the highest precedence followed by the concatenation operator \u201c.\u201d followed by the union operator \u201c+\u201d or \u201c|\u201d.<\/p>\n

       <\/p>\n

      Figures 4.6 a, b and c give the automata for the simple regular expression without involving any regular expression operators.<\/p>\n

      \"\"<\/p>\n

      Figure 4.6 a, is an automata corresponding to the regular expression \u201ca\u201d. The regular expression \u201ca\u201d corresponds to only one string \u201ca\u201d. This is given as an automaton with two states and one edge labeled \u201ca\u201d that goes from start to final state. Figure 4.6 b is an automata corresponding to the regular expression \u201c\u03b5\u201d. The difference between figures 4.6 a and 4.6b is just that the edge is labeled \u2018\u03b5\u2019 instead of \u2018a\u2019. Figure 4.6c corresponds to automata for the \u03a6 string. There is no edge from the start to the final state and hence no path exists from start to the final state. Thus, this automaton doesn\u2019t accept any string. The constraint that is posed in the construction is that there is exactly one final state.<\/p>\n

       <\/p>\n

      A regular expression is formed using the base expression as an alphabet and connecting them using regular expression operators. Base expression is what has been discussed in Figure 4.6 (a-c). A regular expression can be formed using anyone of the operators, +, ., * which indicates union, concatenation or kleene closure. If R1, R2 are base regular expressions, another regular expression could be formed in one of the following ways:<\/p>\n

       <\/p>\n\n\n\n\n\n
      R3<\/td>\n= R1+R2<\/td>\n(4.2)<\/td>\n<\/tr>\n
      R4<\/td>\n= R1 . R2<\/td>\n(4.3)<\/td>\n<\/tr>\n
      R5<\/td>\n= R1*<\/td>\n(4.4)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

      Equation (4.2) indicates a new regular expression R3 formed by performing union of two regular expressions. The construction of the \u03f5-NFA is given in figure 4.7<\/p>\n

      \"\"<\/p>\n

      \n

      Let M1 and M2 be the automata corresponding to R1 and R2 respectively. A new automaton with \u03b5 transitions is constructed by adding two new states, one start and one final state. \u03b5 transitions are defined from the new start state to the existing automata M1, M2\u2019s start state. \u03b5 transitions are also defined from the final states of M1 and M2 to the new final state. Thus, if a string belongs to the expression R1, then it follows the path through M1 by suffixing and prefixing the string with \u03b5. On the other hand if a string corresponds to regular expression R2, then it follows the path of M2. Thus this new NFA accepts strings belonging to R1 and R2,\u00a0which is the implication of the union operator. To construct automata for other expressions, a-NFA\u00a0\u00a0<\/span>Equation 4.3 indicates the concatenation operator, where regular expression R4 corresponds to the strings of R1 followed by R2. The corresponding automata <\/span>is given in figure 4.8<\/span><\/p>\n<\/div>\n

      \"\"<\/p>\n

      \"\"<\/p>\n

      Summary:<\/strong><\/p>\n

       <\/p>\n

      This module discussed the concepts of DFA, NFA and \u03b5-NFA and their ways of defining patterns for string matching. However, conversion from regular expression to automata may be required, and this module focused on the first step in converting regular expression to \u03f5-NFA.<\/p>\n","protected":false},"author":4,"menu_order":4,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-42","chapter","type-chapter","status-publish","hentry"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/42","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":1,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/42\/revisions"}],"predecessor-version":[{"id":52,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/42\/revisions\/52"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/42\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=42"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=42"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=42"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=42"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}