Acceptance Criteria

Acceptance Criteria

Pushdown automata (PDA) are a type of computational model that accept context-free languages. Understanding how PDAs accept input is crucial for grasping their role in the Chomsky hierarchy. This section will explore the different acceptance criteria for PDAs, including acceptance by final state and acceptance by empty stack.

Acceptance by Final State

A pushdown automaton accepts an input string by final state if it reaches a designated accepting state after processing the entire input. This means that the automaton must consume all input symbols and end in an accepting state.

Example of Acceptance by Final State

Consider a PDA that accepts the language L = { a^n b^n | n ≥ 0 }. This language consists of strings with an equal number of a's followed by an equal number of b's.

The PDA can be defined with the following components:

• States: Q = { q0, q1, q_accept }
• Input alphabet: Σ = { a, b }
• Stack alphabet: Γ = { Z, A }
• Transition function: δ
• Initial state: q0
• Initial stack symbol: Z
• Accepting state: q_accept

The transition function δ can be defined as follows:

δ(q0, a, Z) = (q0, A Z)  // Push A onto the stack for each a read
δ(q0, a, A) = (q0, A A)  // Push A onto the stack for each a read
δ(q0, b, A) = (q1, A)     // Pop A from the stack for each b read
δ(q1, b, A) = (q1, A)     // Continue popping A for each b read
δ(q1, ε, Z) = (q_accept, Z)  // Accept if stack is back to Z

In this example, the PDA starts in state q0 and pushes A onto the stack for each a it reads. When it reads a b, it transitions to state q1 and pops A from the stack. If the input string has equal numbers of a's and b's, the PDA will eventually return to the initial stack symbol Z in the accepting state q_accept.

Acceptance by Empty Stack

A pushdown automaton accepts an input string by empty stack if it empties its stack after processing the entire input. This means that the PDA can end in any state as long as the stack is empty.

Example of Acceptance by Empty Stack

Consider the same PDA that accepts the language L = { a^n b^n | n ≥ 0 }. However, this time we will define it to accept by empty stack.

The transition function δ can be modified as follows:

δ(q0, a, Z) = (q0, A Z)  // Push A onto the stack for each a read
δ(q0, a, A) = (q0, A A)  // Push A onto the stack for each a read
δ(q0, b, A) = (q0, A)     // Pop A from the stack for each b read
δ(q0, b, Z) = (q0, Z)     // Do not pop Z
δ(q0, ε, A) = (q0, ε)     // Pop A from the stack if input is empty
δ(q0, ε, Z) = (q_accept, Z)  // Accept if stack is empty

In this case, the PDA still pushes A onto the stack for each a it reads. When it reads a b, it can either pop A or not pop Z. To accept the input, the PDA must eventually pop all A's from the stack, and it can do so by reading ε (the empty string) when the input is exhausted. If the stack is empty when it reaches the accepting state, the input is accepted.

Comparing the Two Acceptance Criteria

Acceptance by final state and acceptance by empty stack are two different criteria for a PDA to accept an input string. It is important to note that both criteria can accept the same languages, but they do so in different ways. The choice of acceptance criterion can affect the design of the PDA.

Example of Language Acceptance

Let us consider the language L = { a^n b^n | n ≥ 0 } again. A PDA can be designed to accept this language by either final state or empty stack. Both designs will be valid, but the transitions and states may differ based on the acceptance criterion chosen.

Closure Properties of PDAs

It is also important to understand the closure properties of the languages accepted by PDAs. The languages accepted by PDAs are closed under certain operations:

• Union: If L1 and L2 are languages accepted by PDAs, then L1 ∪ L2 is also accepted by a PDA.
• Concatenation: If L1 and L2 are languages accepted by PDAs, then L1L2 is also accepted by a PDA.
• Kleene Star: If L is a language accepted by a PDA, then L* is also accepted by a PDA.

However, the languages accepted by PDAs are not closed under intersection or complementation.

Practical Implications

Understanding the acceptance criteria of PDAs has practical implications in computer science. For example, programming languages that are context-free can be parsed using PDAs. Compilers often use PDAs to check the syntax of programming languages, ensuring that the code adheres to the language rules.

In summary, PDAs can accept input strings through two main criteria: acceptance by final state and acceptance by empty stack. Each criterion has its own implications for the design and functionality of the PDA. It is essential to understand these criteria to effectively work with PDAs and context-free languages.

Summary

• Pushdown automata can accept input by final state or empty stack.
• Acceptance by final state requires reaching an accepting state after consuming all input.
• Acceptance by empty stack requires the stack to be empty after processing the input.
• Both acceptance criteria can accept the same languages but may use different designs.
• Languages accepted by PDAs are closed under union, concatenation, and Kleene star.

Check your understanding

1. What is the difference between acceptance by final state and acceptance by empty stack?
2. Provide an example of a language that can be accepted by a PDA using both acceptance criteria.
3. What are the closure properties of languages accepted by PDAs?
4. Why is it important to choose an acceptance criterion when designing a PDA?