Designing a Login Validation System Using Finite State Machines

In this scenario, you are working for a software development team that is building a secure login system for a web application. The system must validate user input for usernames and passwords using strict formatting rules. To ensure efficiency and reliability, your team decides to implement the validation logic using finite state machines.

The requirements for the system are as follows:

• Usernames must start with a letter and may contain letters and digits.
• Passwords must be at least 8 characters long and include at least one digit, one uppercase letter, and one special character.
• The system must reject any input that does not conform to these rules.

Task 1

Define two formal languages ([latex]L_{1}[/latex] and [latex]L_{2}[/latex]) for valid usernames and passwords and their associated alphabets.

Task 2

Construct grammars for each language. For the passwords grammar, ensure additional semantic checks are applied to ensure the presence of required character types.

Task 3

Design FSMs to recognize each language. The FSM for [latex]L_{1}[/latex] starts in an initial state, transitions to a valid state upon reading a letter, and continues accepting letters or digits. The FSM for [latex]L_{2}[/latex] uses multiple states to track the presence of required character types and the total length.

Task 4

Test various input strings that users may enter against the FSMs and provides feedback to users.

Task 5

Determine the time validation per character for the FSM and explain the benefit of the speed. Compare the FSM-based validation to regular expression engines and discuss how FSMs are faster and easier to debug.