L3 Formal Languages

Formal languages are precisely defined systems of symbols and rules. They allow computers to recognise patterns, validate input, understand program structure, and translate human-written instructions into actions.

Unlike natural language, a formal language aims to remove ambiguity. A computer must be able to determine whether an input follows the rules of the language.

Key Concepts

Alphabet: The permitted symbols in a language.

String: A sequence of symbols from the alphabet.

Language: The set of all strings accepted by a particular set of rules.

Regular expression: A pattern used to describe or recognise strings.

Regular language: A language that can be described by a regular expression or recognised by a finite-state automaton.

Finite-state automaton: A model that reads one input symbol at a time and moves between a fixed number of states.

Context-free grammar: A set of production rules used to describe structured or nested languages.

Tokenising: Breaking source text into tokens such as keywords, identifiers, numbers, operators, and punctuation.

Parsing: Checking whether a sequence of tokens follows the grammar of the language.

Syntax tree: A tree representing the structure of a valid expression, statement, or program.

Model Answers

Task Best-fitting mechanism

Find dates inside a large text file Regular expression

Check whether a binary message contains an even number of 1s FSA

Recognise identifiers and numbers during tokenising Regular expression or FSA

Check matching and nested brackets CFG and parser

Model ticket-machine screens and buttons FSA

Check a complete programming statement CFG and parser

1. Dates and token patterns can usually be described using regular expressions.

2. Fixed-state patterns and interface states can be represented using FSAs.

3. Nested brackets and complete program structures require grammars and parsing.

4. Every regular expression can be represented by an equivalent FSA.

5. Tokens may be individually valid but placed in an invalid order.

6. Syntax checking cannot prove that the program is useful, safe, or logically correct.

ANSWERS

^[A-Z]{2}:[0-9]{4}/[A-Z]$

• ^ marks the start.

• [A-Z]{2} requires two uppercase letters.

• : matches the colon.

• [0-9]{4} requires four digits.

• / matches the forward slash.

• [A-Z] requires one uppercase letter.

• $ marks the end.

Accepted:

RK:2048/A

AQ:0192/C

XX:9999/Z

Rejected:

rK:2048/A

RK:248/A

RK:2048/AB

The expression can prevent incorrectly formatted identifiers from being entered into a system. During tokenising, it could recognise a complete sensor identifier as one token.

Its strength is fast, consistent pattern recognition. Its limitation is that it only checks format. It cannot confirm that the sensor actually exists.

Next steps

Hover over each part of the expression to view RegExr’s explanation.

Change one valid identifier at a time to test what happens when you add a lowercase letter, remove a digit, or add an extra letter.

Trainsylvania FSA — Answers

1. Shortest route to Harbour:
   ABBAB — 5 train rides
   Airport → West → Central → Midway → North → Harbour.

2. Where does BBABBA finish?
   It finishes back at Airport Station:
   Airport → South → Factory → Airport → South → Factory → Airport.

3. Two routes to Harbour:
   
   

   • Shortest: ABBAB

   • Longer route: BABABABAABBAB — 13 train rides

4. BABA forms a loop that returns to Airport. Repeating the loop twice and then taking ABBAB still finishes at Harbour.

Finite-State Automata in Action Using JFLAP

Activity: Even Number of b Symbols

Create a finite-state automaton over the alphabet:

{a, b}

The automaton must accept a string only when it contains an even number of b symbols.

Building the FSA in JFLAP

1. Create a new automaton

Open JFLAP and select Finite Automaton. This opens the editor containing tools for creating states, transitions, and initial or accepting states.

2. Create two states

Select the State Creator tool and click twice on the workspace.

JFLAP will create:

• q0 — an even number of bs has been read

• q1 — an odd number of bs has been read

3. Set the start and accepting state

Select the Attribute Editor tool and right-click q0.

Mark q0 as:

• Initial

• Final

It is the initial state because the automaton begins with zero bs, and zero is even. A final state appears with a double circle.

Do not mark q1 as final.

4. Add the transitions

Select the Transition Creator tool and add these transitions:

From Input To Reason

q0 a q0 Reading a does not change the number of bs

q1 a q1 Reading a does not change the number of bs

q0 b q1 One more b changes even to odd

q1 b q0 One more b changes odd to even

To create a loop, select the transition tool and click the state itself. To connect two states, drag from the first state to the second, type the transition symbol, and press Enter.

Your finished FSA should follow this structure:

               b

          ┌─────────────┐

          ▼             │

→ ((q0: even))       (q1: odd)

      ↺ a               ↺ a

          │             ▲

          └──────b──────┘

q0 is both the start and accepting state.

Testing the FSA

1. Select Input → Multiple Run.

2. Enter each test string on a separate row.

3. Use Enter Lambda to enter the empty string.

4. Select Run Inputs.

5. JFLAP will display Accept or Reject for each string.

Expected results

Input Number of bs Expected result

Empty string "" 0 Accept

a 0 Accept

b 1 Reject

bb 2 Accept

ababa 2 Accept

aab 1 Reject

bbabb 4 Accept

To watch a string being processed one symbol at a time, select Input → Step with Closure, enter the string, and repeatedly select Step. JFLAP highlights the state reached after each input symbol.

Finite-State Automata in Action Using Finsm.io

Activity: Even Number of b Symbols

Create a finite-state automaton over the alphabet:

{a, b}

The automaton must accept a string only when it contains an even number of b symbols.

1. Create two states

Open finsm.io in Build mode.

• Hold Shift and click an empty space to create the first state.

• Repeat to create a second state.

• Shift-click each state label and rename them:

  • q0 – even

  • q1 – odd

In finsm.io, states are created with Shift-click, moved by dragging, and renamed by Shift-clicking their labels.

2. Make q0 an accepting state

Click q0 once to select it, then press F.

It should now appear as a double circle. q0 is accepting because the machine has read an even number of bs. At the beginning it has read zero bs, and zero is even.

Do not make q1 an accepting state.

3. Add the transitions

Hover over the edge of a state until a + appears. Drag from that state to the destination state. Shift-click the arrow label to enter its input symbol. To create a loop, drag the arrow back onto the same state.

Create these four transitions:

From Input To Reason

q0 a q0 Reading a does not change the number of bs

q1 a q1 Reading a does not change the number of bs

q0 b q1 Another b changes even to odd

q1 b q0 Another b changes odd to even

Your automaton should follow this pattern:

                b

        ┌─────────────────┐

        ▼                 │

→ ((q0: even))        (q1: odd)

      ↺ a                ↺ a

        │                 ▲

        └────────b────────┘

4. Set the start state

Select Simulate mode and choose DFA at the top left.

Click q0 to make it the start state. In DFA mode, clicking a state makes it the single starting state.

5. Enter and test strings

At the bottom of Simulate mode:

1. Select + to create a new input tape.

2. Select the pencil beside the tape.

3. Enter a test string and press Enter.

4. Select the tape and press the right-arrow key to process one symbol at a time.

The active state is highlighted as the input is processed.

For the empty string, create a tape but leave it blank. Because the automaton starts in accepting state q0, the empty string is accepted.

Expected results

Input Number of bs Result

Empty string "" 0 Accept

a 0 Accept

b 1 Reject

bb 2 Accept

ababa 2 Accept

aab 1 Reject

bbabb 4 Accept

For example, ababa follows:

q0 → q0 → q1 → q1 → q0 → q0

 a    b    a    b    a

It finishes in q0, so it is accepted.

Model Answers

1. The alphabet is {a, b}.

2. One state represents no useful ending, one represents that the latest symbol is a, and one represents that the string currently ends in ab.

3. The “no useful ending” state is the start state.

4. The state representing “ends in ab” is the accepting state.

5. Reading a moves the automaton to the state showing that the latest symbol is a.

6. Reading b then moves it to the accepting state because the string now ends in ab.

7. bbab finishes in the accepting state, so it is accepted.

8. Three states are needed to remember whether the input has no useful ending, ends in a, or ends in ab.

9. It only checks the final two symbols. It does not understand the meaning of the string or recognise nested structures.

Required Transitions

From state Input To state

Start a Ends in a

Start b Start

Ends in a a Ends in a

Ends in a b Ends in ab

Ends in ab a Ends in a

Ends in ab b Start

Model Answers

1. The start symbol is <program>.

2. The non-terminals are <program>, <command>, <direction>, and <number>.

3. Terminals include MOVE, TURN, LEFT, RIGHT, REPEAT, {, }, and ;.

4. Production rules describe how each non-terminal can be expanded.

5. It matches <command> ; <program>.

6. REPEAT must be followed by a number before the opening brace.

7. <program> can contain a <command>, and a REPEAT command contains another <program>.

8. The grammar can describe recursive and arbitrarily nested structures.

9. The parser would produce a parse tree or abstract syntax tree representing the program’s structure.

Context-free grammars are designed for hierarchical structures in which expressions or statements may contain more expressions or statements.

Model Answers

1. Tokens include total, =, price, +, and tax.

2. An Assign node represents the assignment statement.

3. The addition is represented by a BinOp node containing price, the Add operator, and tax.

4. The operator changes from Add to Mult, while the overall tree structure remains similar.

5. The parser reports a SyntaxError because an expression is required after =.

6. An AST clearly represents the structure of the code, making it easier to analyse, check, translate, or modify.

7. No. The AST only shows that the syntax is valid. Checking whether price and tax exist happens later during execution or semantic analysis.