# Automata Derivation

Automata Derivation with automata tutorial, finite automata, dfa, nfa, regexp, transition diagram in automata, transition table, theory of automata, examples of dfa, minimization of dfa, non deterministic finite automata, etc.

# Derivation

Derivation is a sequence of production rules. It is used to get the input string through these production rules. During parsing, we have to take two decisions. These are as follows:

• We have to decide the non-terminal which is to be replaced.
• We have to decide the production rule by which the non-terminal will be replaced.

We have two options to decide which non-terminal to be placed with production rule.

## 1. Leftmost Derivation:

In the leftmost derivation, the input is scanned and replaced with the production rule from left to right. So in leftmost derivation, we read the input string from left to right.

### Example:

Production rules:

```E = E + E
E = E - E
E = a | b
```

Input

```a - b + a
```

The leftmost derivation is:

```E = E + E
E = E - E + E
E = a - E + E
E = a - b + E
E = a - b + a
```

## 2. Rightmost Derivation:

In rightmost derivation, the input is scanned and replaced with the production rule from right to left. So in rightmost derivation, we read the input string from right to left.

### Example

Production rules:

```E = E + E
E = E - E
E = a | b
```

Input

```a - b + a
```

The rightmost derivation is:

```E = E - E
E = E - E + E
E = E - E + a
E = E - b + a
E = a - b + a
```

When we use the leftmost derivation or rightmost derivation, we may get the same string. This type of derivation does not affect on getting of a string.

## Examples of Derivation:

### Example 1:

Derive the string "abb" for leftmost derivation and rightmost derivation using a CFG given by,

```S → AB | ε
A → aB
B → Sb
```

Solution:

Leftmost derivation:

Rightmost derivation:

### Example 2:

Derive the string "aabbabba" for leftmost derivation and rightmost derivation using a CFG given by,

```S → aB | bA
S → a | aS | bAA
S → b | aS | aBB
```

Solution:

Leftmost derivation:

```S
aB            S → aB
aaBB          B → aBB
aabB          B → b
aabbS         B → bS
aabbaB        S → aB
aabbabS       B → bS
aabbabbA      S → bA
aabbabba      A → a
```

Rightmost derivation:

```S
aB            S → aB
aaBB          B → aBB
aaBbS         B → bS
aaBbbA        S → bA
aaBbba        A → a
aabSbba       B → bS
aabbAbba      S → bA
aabbabba      A → a
```

### Example 3:

Derive the string "00101" for leftmost derivation and rightmost derivation using a CFG given by,

```S → A1B
A → 0A | ε
B → 0B | 1B | ε
```

Solution:

Leftmost derivation:

```S
A1B
0A1B
00A1B
001B
0010B
00101B
00101
```

Rightmost derivation:

```S
A1B
A10B
A101B
A101
0A101
00A101
00101
```

Next TopicDerivation Tree
The text passage is about the concept of derivation in the theory of automata, specifically focusing on leftmost and rightmost derivations with examples.
no_question

the passage does not contain any mathematical questions or problems that require solving. it provides explanations and examples of derivations but does not ask the reader to solve any specific problems.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Automata Derivation

Automata Derivation with automata tutorial, finite automata, dfa, nfa, regexp, transition diagram in automata, transition table, theory of automata, examples of dfa, minimization of dfa, non deterministic finite automata, etc.

# Derivation

Derivation is a sequence of production rules. It is used to get the input string through these production rules. During parsing, we have to take two decisions. These are as follows:

• We have to decide the non-terminal which is to be replaced.
• We have to decide the production rule by which the non-terminal will be replaced.

We have two options to decide which non-terminal to be placed with production rule.

## 1. Leftmost Derivation:

In the leftmost derivation, the input is scanned and replaced with the production rule from left to right. So in leftmost derivation, we read the input string from left to right.

### Example:

Production rules:

```E = E + E
E = E - E
E = a | b
```

Input

```a - b + a
```

The leftmost derivation is:

```E = E + E
E = E - E + E
E = a - E + E
E = a - b + E
E = a - b + a
```

## 2. Rightmost Derivation:

In rightmost derivation, the input is scanned and replaced with the production rule from right to left. So in rightmost derivation, we read the input string from right to left.

### Example

Production rules:

```E = E + E
E = E - E
E = a | b
```

Input

```a - b + a
```

The rightmost derivation is:

```E = E - E
E = E - E + E
E = E - E + a
E = E - b + a
E = a - b + a
```

When we use the leftmost derivation or rightmost derivation, we may get the same string. This type of derivation does not affect on getting of a string.

## Examples of Derivation:

### Example 1:

Derive the string "abb" for leftmost derivation and rightmost derivation using a CFG given by,

```S → AB | ε
A → aB
B → Sb
```

Solution:

Leftmost derivation:

Rightmost derivation:

### Example 2:

Derive the string "aabbabba" for leftmost derivation and rightmost derivation using a CFG given by,

```S → aB | bA
S → a | aS | bAA
S → b | aS | aBB
```

Solution:

Leftmost derivation:

```S
aB            S → aB
aaBB          B → aBB
aabB          B → b
aabbS         B → bS
aabbaB        S → aB
aabbabS       B → bS
aabbabbA      S → bA
aabbabba      A → a
```

Rightmost derivation:

```S
aB            S → aB
aaBB          B → aBB
aaBbS         B → bS
aaBbbA        S → bA
aaBbba        A → a
aabSbba       B → bS
aabbAbba      S → bA
aabbabba      A → a
```

### Example 3:

Derive the string "00101" for leftmost derivation and rightmost derivation using a CFG given by,

```S → A1B
A → 0A | ε
B → 0B | 1B | ε
```

Solution:

Leftmost derivation:

```S
A1B
0A1B
00A1B
001B
0010B
00101B
00101
```

Rightmost derivation:

```S
A1B
A10B
A101B
A101
0A101
00A101
00101
```

Next TopicDerivation Tree
user
The text passage is about the concept of derivation in the theory of automata, specifically focusing on leftmost and rightmost derivations with examples.

TYPE: NO_QUESTION

The passage does not contain any mathematical questions or problems that require solving. It provides explanations and examples of derivations but does not ask the reader to solve any specific problems.