8.1 Languages and Grammars

Basic Skills

1. Define a formal language over the alphabet [latex]\Sigma = \{ a, b \}[/latex] that includes all strings with exactly two a’s. List three valid strings and two invalid strings.
2. Identify the alphabet used in the following set of strings: {101, 110, 000, 111}. What is the formal definition of the language these strings belong to?
3. Given the grammar [latex]S \rightarrow aSb \mid \epsilon[/latex], generate all valid strings of length 2, 4, and 6. Explain why the grammar produces balanced strings.
4. Determine whether the string aabbb belongs to the language defined by the grammar [latex]S \rightarrow aSb \mid ab[/latex]. Justify your answer by showing the derivation steps or explaining why it fails.
5. Explain the difference between a formal language and a natural language. Provide one example of each and describe why formal languages are preferred in computing.

Applications

6. A compiler must validate source code identifiers that follow specific rules: they must begin with a letter and may contain letters, digits, and underscores. Define a formal language over the alphabet [latex]\Sigma[/latex] = {a to z, A to Z, 0 to 9, _} that captures this rule. Write a grammar that generates valid identifiers and explain how it ensures correctness.
7. A messaging app filters user input to allow only strings that contain alternating vowels and consonants. Define a formal language over [latex]\Sigma = \{ a, e, i, o, u, b, c, d, f, g \}[/latex] that includes strings like ab, ec, idg. Design a grammar that generates such strings and describe how it could be used in input validation.
8. A network protocol uses a handshake sequence that must follow the pattern "ping-pong-ping". Define a grammar that generates this sequence and explain how a finite state machine could be used to validate it during communication.
9. A password policy requires that passwords begin with a digit, followed by at least one uppercase letter, and end with a special character. Define a formal language over [latex]\Sigma[/latex] = {0 to 9, A to Z, !, @, #} that captures this rule. Write a grammar and explain how it enforces the structure of valid passwords.
10. An e-commerce site uses product codes that follow the format: two letters, three digits, and one special character. Define a grammar that generates valid product codes over [latex]\Sigma[/latex] = {A to Z, 0 to 9, #, @, &}. Explain how this grammar could be used to validate product entries in a database.

Challenge Problems

11. Prove or disprove: The language defined by the grammar [latex]S \rightarrow aS \mid Sb \mid \epsilon[/latex] generates all strings with equal numbers of [latex]a[/latex]’s and [latex]b[/latex]’s. Provide a counterexample or a derivation that supports your conclusion.
12. Design a grammar that generates all strings over [latex]\Sigma = \{ 0, 1 \}[/latex] that do not contain the substring 11. Explain your production rules and demonstrate how the grammar avoids consecutive 1s.
13. Given the language [latex]L = \{ w \in \{ a, b \}^{*} \mid w[/latex] contains more [latex]a[/latex]’s than [latex]b[/latex]’s[latex]\}[/latex], propose a grammar that generates this language. Justify your design and explain how it ensures the count condition.
14. Construct a grammar that generates palindromes over [latex]\Sigma = \{ 0, 1 \}[/latex]. A palindrome is a string that reads the same forward and backward (e.g., 101, 0110). Show how your grammar handles both even- and odd-length strings.
15. Compare two grammars [latex]G_{1}: S \rightarrow aSb \mid \epsilon[/latex] and [latex]G_{2}: S \rightarrow ab \mid aSb[/latex]. Determine whether they generate the same language. Provide examples and explain any differences in the structure or output.

8.2 Finite State Machines, Languages and Automata

Basic Skills

16. Define the components of a finite state machine. List and briefly describe each part: states, input alphabet, transition function, start state, and accepting states.
17. Consider the FSM with states [latex]\{ q_{0}, q_{1} \}[/latex], input alphabet [latex]\Sigma = \{ 0, 1 \}[/latex], transitions [latex]q_{0} \rightarrow q_{1}[/latex] on input 1 and [latex]q_{1} \rightarrow q_{0}[/latex] on input 0, [latex]q_{0}[/latex] is the start state, and [latex]q_{1}[/latex] is the accepting state. Determine whether the string 10 is accepted by the FSM.
18. Construct a transition table for an FSM that accepts binary strings ending in 01. Define the states, transitions, and accepting state.
19. Explain the difference between a deterministic finite automaton (DFA) and a nondeterministic finite automaton (NFA). Provide one example of a situation where an NFA might be easier to design.
20. Determine whether the string abba is accepted by the FSM defined by the following grammar: [latex]S \rightarrow aA, A \rightarrow bB, B \rightarrow bC, C \rightarrow a[/latex]. Show the derivation steps or explain why the string is rejected.

Applications

21. A vending machine accepts coins in denominations of 5 cents, 10 cents, and 25 cents. It dispenses a product when the total reaches 50 cents. Design a finite-state machine that models the coin-input process. Define the states, transitions, and accepting state, and explain how the FSM ensures correct dispensing.
22. A login system uses an FSM to validate password input. The password must contain at least one uppercase letter, one digit, and one special character. Describe how the FSM would track these conditions across states. Explain how the FSM transitions based on character types and how it determines acceptance.
23. An elevator control system uses a finite state machine to manage floor transitions. Each state represents a floor, and inputs are "up" or "down" commands. Design the FSM for a 3-floor building and explain how it handles invalid transitions (e.g., "up" from the top floor).
24. A traffic light controller cycles through green, yellow, and red lights in sequence. Model this system using a finite state machine. Define the states, transitions, and how timing or external input (e.g., pedestrian button) could affect the FSM.
25. A spell checker uses an FSM to detect common typos in words like "receive" and "accommodate". Describe how the FSM can be used to recognize incorrect sequences and suggest corrections. Explain how the FSM transitions through character inputs and flags errors.

Challenge Problems

26. Design a finite state machine that accepts binary strings containing an even number of 0s and an odd number of 1s. Define the states, transitions, and accepting conditions. Justify how your FSM tracks both conditions simultaneously.
27. Prove or disprove: Every regular language can be recognized by a deterministic finite automaton. Provide a formal argument or counterexample and explain the implications for automata design.
28. Convert the following FSM into a regular expression: States: [latex]\{ q_{0}, q_{1}, q_{2} \}[/latex]; Start state: [latex]q_{0}[/latex]; Accepting state: [latex]q_{2}[/latex]; Transitions: [latex]q_{0} \rightarrow q_{1}[/latex] on [latex]a[/latex], [latex]q_{1} \rightarrow q_{2}[/latex] on [latex]b[/latex], [latex]q_{2} \rightarrow q_{1}[/latex] on [latex]a[/latex]. Describe the language accepted and explain your conversion process.
29. Construct a nondeterministic finite automaton that accepts strings over [latex]\Sigma = \{ 0, 1 \}[/latex] where the third symbol from the end is a 1. Explain why an NFA is more efficient than a DFA for this task.
30. Given a finite state machine, prove whether it is minimal (i.e., has the smallest number of states possible for the language it accepts). Describe the minimization process and apply it to a sample FSM of your choice.