Exercise 1: String Validator Using Finite State Machine

The objective of this exercise is to simulate a finite state machine that validates strings based on a simple grammar.

Your task is to write a program (using pseudocode or a programming language of your choice) that accepts a string and checks whether it belongs to a language defined by the following rules:

• The string must start with a letter.
• It may contain letters and digits.
• It must be at least 3 characters long.

Implement the FSM using states and transitions, and print whether the string is accepted or rejected.

Exercise 2: Grammar-Based String Generator

The objective of this exercise is to practice generating strings from a formal grammar.

Your task is to write a program (using pseudocode or a programming language of your choice) that uses a context-free grammar to generate valid strings.

Define a grammar such as [latex]S \rightarrow aSb \mid \epsilon[/latex]

Your program should recursively generate strings of the form [latex]a^{n} b^{n}[/latex] (e.g., ab, aabb, aaabbb) and print all valid strings up to a given depth.

Exercise 3: FSM Transition Table Simulator

The objective of this exercise is to model a finite state machine using a transition table.

Your task is to create a program (using pseudocode or a programming language of your choice) that:

• Accepts a transition table as input (states, input symbols, next states).
• Accepts a string of input symbols.
• Simulates the FSM and prints the final state and whether the string is accepted.

Include support for defining accepting states and a start state.

Exercise 4: Regular Expression to FSM Converter

The objective of this exercise is to explore the relationship between regular expressions and finite automata.

Your task is to write a program (using pseudocode or a programming language of your choice) that:

• Accepts a regular expression (e.g., a*b+).
• Converts it into an equivalent FSM structure (states and transitions).
• Displays the FSM as a transition diagram or table.

Exercise 5: Login Validator Using FSM

The objective of this exercise is to apply FSMs to a real-world scenario.

Your task is to simulate a login validator (using pseudocode or a programming language of your choice) that:

• Accepts a username and password.
• Validates the username using an FSM that checks for a letter followed by letters or digits.
• Validates the password using an FSM that checks for at least one digit, one uppercase letter, and one special character.

Print whether the login credentials are valid based on FSM acceptance.