Question

Like TG, a PDA can also be non-deterministic
True (Page 111)​

Answer 1

Answer:

here is your answer hope it helps ☺️

Explanation:

We have already discussed finite automata. But finite automata can be used to accept only regular languages.

Pushdown Automata is a finite automata with extra memory called stack which helps Pushdown automata to recognize Context Free Languages.

A Pushdown Automata (PDA) can be defined as :

Q is the set of states

∑is the set of input symbols

Γ is the set of pushdown symbols (which can be pushed and popped from stack)

q0 is the initial state

Z is the initial pushdown symbol (which is initially present in stack)

F is the set of final states

δ is a transition function which maps Q x {Σ ∪ ∈} x Γ into Q x Γ*. In a given state, PDA will read input symbol and stack symbol (top of the stack) and move to a new state and change the symbol of stack.

Instantaneous Description (ID)

Instantaneous Description (ID) is an informal notation of how a PDA “computes” a input string and make a decision that string is accepted or rejected.

A ID is a triple (q, w, α), where:

1. q is the current state.

2. w is the remaining input.

3.α is the stack contents, top at the left.

Turnstile notation

⊢ sign is called a “turnstile notation” and represents

one move.

⊢* sign represents a sequence of moves.

Eg- (p, b, T) ⊢ (q, w, α)

This implies that while taking a transition from state p to state q, the input symbol ‘b’ is consumed, and the top of the stack ‘T’ is replaced by a new string ‘α’

Example : Define the pushdown automata for language {anbn | n > 0}

Solution : M = where Q = { q0, q1 } and Σ = { a, b } and Γ = { A, Z } and &delta is given by :

&delta( q0, a, Z ) = { ( q0, AZ ) }

&delta( q0, a, A) = { ( q0, AA ) }

&delta( q0, b, A) = { ( q1, ∈) }

&delta( q1, b, A) = { ( q1, ∈) }

&delta( q1, ∈, Z) = { ( q1, ∈) }

Let us see how this automata works for aaabbb

Answer 2

Answer:

1. [20 points] For each of the following, circle TRUE if the statement is always correct.

Otherwise, circle FALSE

(a) TRUE FALSE — If a language L is accepted by a nondeterministic finite au-

tomaton, then there must be some PDA that also accepts

L.

(b) TRUE FALSE — If L is generated by a context-free grammar that is not a

regular grammar, then L must not be a regular language.

(c) TRUE FALSE — If L1 is a context-free language and L2 is not context-free,

then L1L2 must be context-free.

(d) TRUE FALSE — If L1 is a context-free language and L2 is not context-free,

then L1L2 must not be context-free.

(e) TRUE FALSE — Every context-free language is a nonregular language.

(f) TRUE FALSE — Every nondeterministic PDA can be transformed into an

equivalent deterministic PDA.

(g) TRUE FALSE — We can construct a PDA for the language L = {a

2n

b

n

:

n = 1, 2, 3, . . .} by first constructing an FA for L, and then

converting the FA into a PDA for L.

(h) TRUE FALSE — If w is an input string and T is a transition graph, then T

must either accept or reject w.

(i) TRUE FALSE — If w is an input string and T is a Turing machine, then T

must either accept or reject w.

(j) TRUE FALSE — There is a Turing machine that can take as input any

encoded Turing machine P and any input w for P and

decide if P halts on input w.