# Properties of Context Free Languages and Turing Machines

## Context-Free Grammar (CFG): `S -> aS | b`

A

context-free grammar (CFG)is a formal way to describe the syntax of languages. It consists of:

- A set of
**production rules**, like`S -> aS | b`

, which dictate how strings in the language are formed. **Terminals**: The actual characters in the language (e.g.,`a`

,`b`

).**Non-terminals**: Variables (e.g.,`S`

) that are placeholders for patterns in the language.**Start symbol**: The initial non-terminal that generates strings.

For example, in the rule `S -> aS | b`

, we have:

: A non-terminal that can generate more characters.`S`

and`a`

: Terminals (characters from the language).`b`

`|`

: Means “or”, so`S`

can either become`aS`

or`b`

.

### Example Rule: `S -> aS | b`

This rule generates strings that consist of one or more `a`

s followed by a single `b`

. Here’s how it works:

**Start with**:`S`

**Apply the rule**:`S -> aS`

**Apply the rule again**:`S -> aS`

**Keep applying until you want to stop with**:`S -> b`

Thus, the string `aaab`

is generated by applying the production rules step-by-step.

### Derivations

A sequence of applications of production rules. For the above rule, here’s an example:

- Start with
`S`

. - Apply
`S -> aS`

:

- Apply
`S -> aS`

again:

- Finally, apply
`S -> b`

:

So, the derivation for `aaab`

is:

### Example Strings

Using the rule `S -> aS | b`

, the following strings can be generated:

`b`

(by directly applying`S -> b`

)`ab`

(by applying`S -> aS`

, then`S -> b`

)`aab`

(by applying`S -> aS -> aS -> b`

)`aaab`

,`aaaab`

, and so on (more`a`

s followed by one`b`

).

**Recursion**: The rule`S -> aS`

is recursive because`S`

can call itself. This allows for generating strings with any number of`a`

s.**Termination**: The recursion stops when we use the rule`S -> b`

, ensuring that the string eventually ends with a`b`

.

# String belongs to Grammar or not?

- Start with the S start symbol and choose the closest production that matches to the given string.
- Replace the Variables with its most appropriate production. Repeat the process until the string is generated or until no other productions are left.