In automata theory, a pushdown automaton (PDA) is a variation of finite automaton that can make use of a stack containing data.

Operation[link]

a diagram of the pushdown automaton

Pushdown automata differ from finite state machines in two ways:

1. They can use the top of the stack to decide which transition to take.
2. They can manipulate the stack as part of performing a transition.

Pushdown automata choose a transition by indexing a table by input signal, current state, and the symbol at the top of the stack. This means that those three parameters completely determine the transition path that is chosen. Finite state machines just look at the input signal and the current state: they have no stack to work with. Pushdown automata add the stack as a parameter for choice.

Pushdown automata can also manipulate the stack, as part of performing a transition. Finite state machines choose a new state, the result of following the transition. The manipulation can be to push a particular symbol to the top of the stack, or to pop off the top of the stack. The automaton can alternatively ignore the stack, and leave it as it is. The choice of manipulation (or no manipulation) is determined by the transition table.

Put together: Given an input signal, current state, and stack symbol, the automaton can follow a transition to another state, and optionally manipulate (push or pop) the stack.

In general, pushdown automata may have several computations on a given input string, some of which may be halting in accepting configurations while others are not. Thus we have a model which is technically known as a "nondeterministic pushdown automaton" (NDPDA or NPDA). Nondeterminism means that there may be more than just one transition available to follow, given an input signal, state, and stack symbol. If in every situation only one transition is available as continuation of the computation, then the result is a deterministic pushdown automaton (DPDA), a strictly weaker device.

If we allow a finite automaton access to two stacks instead of just one, we obtain a more powerful device, equivalent in power to a Turing machine. A linear bounded automaton is a device which is more powerful than a pushdown automaton but less so than a Turing machine.

Pushdown automata are equivalent to context-free grammars: for every context-free grammar, there exists a pushdown automaton such that the language generated by the grammar is identical with the language generated by the automaton, which is easy to prove. The reverse is true, though harder to prove: for every pushdown automaton there exists a context-free grammar such that the language generated by the automaton is identical with the language generated by the grammar.

Formal Definition[link]

A PDA is formally defined as a 7-tuple:

Failed to parse (Missing texvc executable; please see math/README to configure.): M=(Q,\ \Sigma,\ \Gamma,\ \delta, \ q_{0},\ Z, \ F)

where

• Failed to parse (Missing texvc executable; please see math/README to configure.): \, Q

is a finite set of states

• Failed to parse (Missing texvc executable; please see math/README to configure.): \,\Sigma

is a finite set which is called the input alphabet

• Failed to parse (Missing texvc executable; please see math/README to configure.): \,\Gamma

is a finite set which is called the stack alphabet

• Failed to parse (Missing texvc executable; please see math/README to configure.): \,\delta

is a finite subset of  Failed to parse (Missing texvc executable; please see math/README to configure.): Q \times  (\Sigma \cup\{\varepsilon\})  \times \Gamma \times Q \times \Gamma^* 

, the transition relation, where Failed to parse (Missing texvc executable; please see math/README to configure.): \Gamma^{*}

denote the set of strings over Failed to parse (Missing texvc executable; please see math/README to configure.): \Gamma
and Failed to parse (Missing texvc executable; please see math/README to configure.): \varepsilon
denotes the empty string.

• Failed to parse (Missing texvc executable; please see math/README to configure.): \,q_{0}\in\, Q

is the start state

• Failed to parse (Missing texvc executable; please see math/README to configure.): \ Z\in\,\Gamma

is the initial stack symbol

• Failed to parse (Missing texvc executable; please see math/README to configure.): F\subseteq Q

is the set of accepting states

An element Failed to parse (Missing texvc executable; please see math/README to configure.): (p,a,A,q,\alpha) \in \delta

is a transition of Failed to parse (Missing texvc executable; please see math/README to configure.): M

. It has the intended meaning that Failed to parse (Missing texvc executable; please see math/README to configure.): M , in state Failed to parse (Missing texvc executable; please see math/README to configure.): p \in Q , with Failed to parse (Missing texvc executable; please see math/README to configure.): a \in \Sigma \cup\{\varepsilon\}

on the input and with Failed to parse (Missing texvc executable; please see math/README to configure.): A \in \Gamma
as topmost stack symbol, may read Failed to parse (Missing texvc executable; please see math/README to configure.): a

, change the state to Failed to parse (Missing texvc executable; please see math/README to configure.): q , pop Failed to parse (Missing texvc executable; please see math/README to configure.): A , replacing it by pushing Failed to parse (Missing texvc executable; please see math/README to configure.): \alpha \in \Gamma^* . The letter Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon

(epsilon) denotes the empty string and the Failed to parse (Missing texvc executable; please see math/README to configure.): (\Sigma \cup\{\varepsilon\})
component of the transition relation is used to formalize that the PDA can either read a letter from the input, or proceed leaving the input untouched.

In many texts the transition relation is replaced by an (equivalent) formalization, where

• Failed to parse (Missing texvc executable; please see math/README to configure.): \,\delta

is the transition function, mapping Failed to parse (Missing texvc executable; please see math/README to configure.): Q \times (\Sigma \cup\{\varepsilon\}) \times \Gamma
into finite subsets of Failed to parse (Missing texvc executable; please see math/README to configure.): Q \times \Gamma^*

.

Here Failed to parse (Missing texvc executable; please see math/README to configure.): \delta(p,a,A)

contains all possible actions in state Failed to parse (Missing texvc executable; please see math/README to configure.): p
with Failed to parse (Missing texvc executable; please see math/README to configure.): A
on the stack, while reading Failed to parse (Missing texvc executable; please see math/README to configure.): a
on the input. One writes Failed to parse (Missing texvc executable; please see math/README to configure.): (q,\alpha) \in \delta(p,a,A)
for the function precisely when Failed to parse (Missing texvc executable; please see math/README to configure.): (p,a,A,q,\alpha) \in\delta
for the relation. Note that finite in this definition is essential.

Computations

a step of the pushdown automaton

In order to formalize the semantics of the pushdown automaton a description of the current situation is introduced. Any 3-tuple Failed to parse (Missing texvc executable; please see math/README to configure.): (p,w,\beta) \in Q \times \Sigma^* \times \Gamma^*

is called an instantaneous description (ID) of Failed to parse (Missing texvc executable; please see math/README to configure.): M

, which includes the current state, the part of the input tape that has not been read, and the contents of the stack (topmost symbol written first). The transition relation Failed to parse (Missing texvc executable; please see math/README to configure.): \delta

defines the step-relation Failed to parse (Missing texvc executable; please see math/README to configure.): \vdash_{M}
of Failed to parse (Missing texvc executable; please see math/README to configure.): M
on instantaneous descriptions. For instruction Failed to parse (Missing texvc executable; please see math/README to configure.): (p,a,A,q,\alpha) \in \delta
there exists a step Failed to parse (Missing texvc executable; please see math/README to configure.): (p,ax,A\gamma) \vdash_{M} (q,x,\alpha\gamma)

, for every Failed to parse (Missing texvc executable; please see math/README to configure.): x\in\Sigma^*

and every Failed to parse (Missing texvc executable; please see math/README to configure.): \gamma\in \Gamma^*

.

In general pushdown automata are nondeterministic meaning that in a given instantaneous description Failed to parse (Missing texvc executable; please see math/README to configure.): (p,w,\beta)

there may be several possible steps. Any of these steps can be chosen in a computation.

With the above definition in each step always a single symbol (top of the stack) is popped, replacing it with as many symbols as necessary. As a consequence no step is defined when the stack is empty.

Computations of the pushdown automaton are sequences of steps. The computation starts in the initial state Failed to parse (Missing texvc executable; please see math/README to configure.): q_{0}

with the initial stack symbol Failed to parse (Missing texvc executable; please see math/README to configure.): Z
on the stack, and a string Failed to parse (Missing texvc executable; please see math/README to configure.): w
on the input tape, thus with initial description Failed to parse (Missing texvc executable; please see math/README to configure.): (q_{0},w,Z)

. There are two modes of accepting. The pushdown automaton either accepts by final state, which means after reading its input the automaton reaches an accepting state (in Failed to parse (Missing texvc executable; please see math/README to configure.): F ), or it accepts by empty stack (Failed to parse (Missing texvc executable; please see math/README to configure.): \varepsilon ), which means after reading its input the automaton empties its stack. The first acceptance mode uses the internal memory (state), the second the external memory (stack).

Formally one defines

1. Failed to parse (Missing texvc executable; please see math/README to configure.): L(M) = \{ w\in\Sigma^* | (q_{0},w,Z) \vdash_M^* (f,\varepsilon,\gamma)

with Failed to parse (Missing texvc executable; please see math/README to configure.): f \in F
and Failed to parse (Missing texvc executable; please see math/README to configure.): \gamma \in \Gamma^* \}
(final state)

1. Failed to parse (Missing texvc executable; please see math/README to configure.): N(M) = \{ w\in\Sigma^* | (q_{0},w,Z) \vdash_M^* (q,\varepsilon,\varepsilon)

with Failed to parse (Missing texvc executable; please see math/README to configure.): q \in Q \}
(empty stack)

Here Failed to parse (Missing texvc executable; please see math/README to configure.): \vdash_M^*

represents the reflexive and transitive closure of the step relation Failed to parse (Missing texvc executable; please see math/README to configure.): \vdash_M
meaning any number of consecutive steps (zero, one or more).

For each single pushdown automaton these two languages need to have no relation: they may be equal but usually this is not the case. A specification of the automaton should also include the intended mode of acceptance. Taken over all pushdown automata both acceptance conditions define the same family of languages.

Theorem. For each pushdown automaton Failed to parse (Missing texvc executable; please see math/README to configure.): M

one may construct a pushdown automaton Failed to parse (Missing texvc executable; please see math/README to configure.): M'
such that Failed to parse (Missing texvc executable; please see math/README to configure.): L(M)=N(M')

, and vice versa, for each pushdown automaton Failed to parse (Missing texvc executable; please see math/README to configure.): M

one may construct a pushdown automaton Failed to parse (Missing texvc executable; please see math/README to configure.): M'
such that Failed to parse (Missing texvc executable; please see math/README to configure.): N(M)=L(M')

Example[link]

The following is the formal description of the PDA which recognizes the language Failed to parse (Missing texvc executable; please see math/README to configure.): \{0^n1^n \mid n \ge 0 \}

by final state:

PDA for Failed to parse (Missing texvc executable; please see math/README to configure.): \{0^n1^n \mid n \ge 0\} (by final state)

Failed to parse (Missing texvc executable; please see math/README to configure.): M=(Q,\ \Sigma,\ \Gamma,\ \delta, \ p,\ Z, \ F) , where

Failed to parse (Missing texvc executable; please see math/README to configure.): Q = \{ p,q,r \}

Failed to parse (Missing texvc executable; please see math/README to configure.): \Sigma = \{0, 1\}

Failed to parse (Missing texvc executable; please see math/README to configure.): \Gamma = \{A, Z\}

Failed to parse (Missing texvc executable; please see math/README to configure.): q_{0} = p

Failed to parse (Missing texvc executable; please see math/README to configure.): F = \{r\}

Failed to parse (Missing texvc executable; please see math/README to configure.): \delta

consists of the following six instructions:

Failed to parse (Missing texvc executable; please see math/README to configure.): (p,0,Z,p,AZ) , Failed to parse (Missing texvc executable; please see math/README to configure.): (p,0,A,p,AA) , Failed to parse (Missing texvc executable; please see math/README to configure.): (p,\epsilon,Z,q,Z) , Failed to parse (Missing texvc executable; please see math/README to configure.): (p,\epsilon,A,q,A) , Failed to parse (Missing texvc executable; please see math/README to configure.): (q,1,A,q,\epsilon) , and Failed to parse (Missing texvc executable; please see math/README to configure.): (q,\epsilon,Z,r,Z) .

In words, in state Failed to parse (Missing texvc executable; please see math/README to configure.): p

for each symbol Failed to parse (Missing texvc executable; please see math/README to configure.): 0
read, one Failed to parse (Missing texvc executable; please see math/README to configure.): A
is pushed onto the stack. Pushing symbol Failed to parse (Missing texvc executable; please see math/README to configure.): A
on top of another Failed to parse (Missing texvc executable; please see math/README to configure.): A
is formalized as replacing top Failed to parse (Missing texvc executable; please see math/README to configure.): A
by Failed to parse (Missing texvc executable; please see math/README to configure.): AA

. In state Failed to parse (Missing texvc executable; please see math/README to configure.): q

for each symbol Failed to parse (Missing texvc executable; please see math/README to configure.): 1
read one Failed to parse (Missing texvc executable; please see math/README to configure.): A
is popped. At any moment the automaton may move from state Failed to parse (Missing texvc executable; please see math/README to configure.): p
to state Failed to parse (Missing texvc executable; please see math/README to configure.): q

, while it may move from state Failed to parse (Missing texvc executable; please see math/README to configure.): q

to accepting state Failed to parse (Missing texvc executable; please see math/README to configure.): r
only when the stack consists of a single Failed to parse (Missing texvc executable; please see math/README to configure.): Z

.

There seems to be no generally used representation for PDA. Here we have depicted the instruction Failed to parse (Missing texvc executable; please see math/README to configure.): (p,a,A,q,\alpha)

by an edge from state Failed to parse (Missing texvc executable; please see math/README to configure.): p
to state Failed to parse (Missing texvc executable; please see math/README to configure.): q
labelled by  Failed to parse (Missing texvc executable; please see math/README to configure.): a; A/\alpha
(read Failed to parse (Missing texvc executable; please see math/README to configure.): a

replace Failed to parse (Missing texvc executable; please see math/README to configure.): A

by Failed to parse (Missing texvc executable; please see math/README to configure.): \alpha

).

Understanding the computation process[link]

accepting computation for Failed to parse (Missing texvc executable; please see math/README to configure.): 0011

The following illustrates how the above PDA computes on different input strings. The subscript Failed to parse (Missing texvc executable; please see math/README to configure.): M

from the step symbol Failed to parse (Missing texvc executable; please see math/README to configure.): \vdash
is here omitted.

(a) Input string = 0011. There are various computations, depending on the moment the move from state Failed to parse (Missing texvc executable; please see math/README to configure.): p

to state Failed to parse (Missing texvc executable; please see math/README to configure.): q
is made. Only one of these is accepting.

(i) Failed to parse (Missing texvc executable; please see math/README to configure.): (p,0011,Z) \vdash (q,0011,Z) \vdash (r,0011,Z)

. The final state is accepting, but the input is not accepted this way as it has not been read.

(ii) Failed to parse (Missing texvc executable; please see math/README to configure.): (p,0011,Z) \vdash (p,011,AZ) \vdash (q,011,AZ)

. No further steps possible.

(iii) Failed to parse (Missing texvc executable; please see math/README to configure.): (p,0011,Z) \vdash (p,011,AZ) \vdash (p,11,AAZ) \vdash (q,11,AAZ)

Failed to parse (Missing texvc executable; please see math/README to configure.):  \vdash (q,1,AZ) \vdash (q,\epsilon,Z)
Failed to parse (Missing texvc executable; please see math/README to configure.):  \vdash (r,\epsilon,Z)

. Accepting computation: ends in accepting state, while complete input has been read.

(b) Input string = 00111. Again there are various computations. None of these is accepting.

(i) Failed to parse (Missing texvc executable; please see math/README to configure.): (p,00111,Z) \vdash (q,00111,Z) \vdash (r,00111,Z)

. The final state is accepting, but the input is not accepted this way as it has not been read.

(ii) Failed to parse (Missing texvc executable; please see math/README to configure.): (p,00111,Z) \vdash (p,0111,AZ) \vdash (q,0111,AZ)

. No further steps possible.

(iii) Failed to parse (Missing texvc executable; please see math/README to configure.): (p,00111,Z) \vdash (p,0111,AZ) \vdash (p,111,AAZ) \vdash (q,111,AAZ)

Failed to parse (Missing texvc executable; please see math/README to configure.):  \vdash (q,11,AZ) \vdash (q,1,Z)
Failed to parse (Missing texvc executable; please see math/README to configure.):  \vdash (r,1,Z)

. The final state is accepting, but the input is not accepted this way as it has not been (completely) read.

PDA and Context-free Languages[link]

Every context-free grammar can be transformed into an equivalent pushdown automaton. The derivation process of the grammar is simulated in a leftmost way. Where the grammar rewrites a nonterminal, the PDA takes the topmost nonterminal from its stack and replaces it by the right-hand part of a grammatical rule (expand). Where the grammar generates a terminal symbol, the PDA reads a symbol from input when it is the topmost symbol on the stack (match). In a sense the stack of the PDA contains the unprocessed data of the grammar, corresponding to a pre-order traversal of a derivation tree.

Technically, given a context-free grammar, the PDA is constructed as follows.

1. Failed to parse (Missing texvc executable; please see math/README to configure.): (1,\varepsilon,A,1,\alpha)

for each rule Failed to parse (Missing texvc executable; please see math/README to configure.): A\to\alpha
(expand)

1. Failed to parse (Missing texvc executable; please see math/README to configure.): (1,a,a,1,\varepsilon)

for each terminal symbol Failed to parse (Missing texvc executable; please see math/README to configure.): a
(match)

As a result we obtain a single state pushdown automaton, the state here is Failed to parse (Missing texvc executable; please see math/README to configure.): 1 , accepting the context-free language by empty stack. Its initial stack symbol equals the axiom of the context-free grammar.

The converse, finding a grammar for a given PDA, is not that easy. The trick is to code two states of the PDA into the nonterminals of the grammar.

Theorem. For each pushdown automaton Failed to parse (Missing texvc executable; please see math/README to configure.): M

one may construct a context-free grammar Failed to parse (Missing texvc executable; please see math/README to configure.): G
such that Failed to parse (Missing texvc executable; please see math/README to configure.): N(M)=L(G)

.

Generalized Pushdown Automaton (GPDA)[link]

A GPDA is a PDA which writes an entire string of some known length to the stack or removes an entire string from the stack in one step.

A GPDA is formally defined as a 6-tuple:

Failed to parse (Missing texvc executable; please see math/README to configure.): M=(Q,\ \Sigma,\ \Gamma,\ \delta, \ q_{0}, \ F)

where Q, Failed to parse (Missing texvc executable; please see math/README to configure.): \Sigma\, , Failed to parse (Missing texvc executable; please see math/README to configure.): \Gamma\, , q₀ and F are defined the same way as a PDA.

Failed to parse (Missing texvc executable; please see math/README to configure.): \,\delta

Failed to parse (Missing texvc executable; please see math/README to configure.): Q \times \Sigma_{\epsilon} \times \Gamma^{*} \longrightarrow P( Q \times \Gamma^{*} )

is the transition function.

Computation rules for a GPDA are the same as a PDA except that the a_i+1's and b_i+1's are now strings instead of symbols.

GPDA's and PDA's are equivalent in that if a language is recognized by a PDA, it is also recognized by a GPDA and vice versa.

One can formulate an analytic proof for the equivalence of GPDA's and PDA's using the following simulation:

Let Failed to parse (Missing texvc executable; please see math/README to configure.): \delta (q₁, w, x₁x₂...x_m) Failed to parse (Missing texvc executable; please see math/README to configure.): \longrightarrow

(q2, y1y2...yn) be a transition of the GPDA 

where Failed to parse (Missing texvc executable; please see math/README to configure.): q_1, q_2 \in Q , Failed to parse (Missing texvc executable; please see math/README to configure.): w \in\Sigma_{\epsilon} , Failed to parse (Missing texvc executable; please see math/README to configure.): x_1, x_2,\ldots,x_m\in\Gamma^{*} , Failed to parse (Missing texvc executable; please see math/README to configure.): m\geq0 , Failed to parse (Missing texvc executable; please see math/README to configure.): y_1, y_2,\ldots,y_n\in\Gamma^{*} , Failed to parse (Missing texvc executable; please see math/README to configure.): n\geq 0 .

Construct the following transitions for the PDA:

Failed to parse (Missing texvc executable; please see math/README to configure.): \delta^{'}

(q₁, w, x₁) Failed to parse (Missing texvc executable; please see math/README to configure.): \longrightarrow

(p1, Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon

)

Failed to parse (Missing texvc executable; please see math/README to configure.): \delta^{'}

(p₁, Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon , x₂) Failed to parse (Missing texvc executable; please see math/README to configure.): \longrightarrow

(p2, Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon

)

Failed to parse (Missing texvc executable; please see math/README to configure.): \vdots

Failed to parse (Missing texvc executable; please see math/README to configure.): \delta^{'}

(p_m-1, Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon , x_m) Failed to parse (Missing texvc executable; please see math/README to configure.): \longrightarrow

(pm, Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon

)

Failed to parse (Missing texvc executable; please see math/README to configure.): \delta^{'}

(p_m, Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon , Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon

) Failed to parse (Missing texvc executable; please see math/README to configure.): \longrightarrow
(pm+1, yn)

Failed to parse (Missing texvc executable; please see math/README to configure.): \delta^{'}

(p_m+1, Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon , Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon

) Failed to parse (Missing texvc executable; please see math/README to configure.): \longrightarrow
(pm+2, yn-1)

Failed to parse (Missing texvc executable; please see math/README to configure.): \vdots

Failed to parse (Missing texvc executable; please see math/README to configure.): \delta^{'}

(p_m+n-1, Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon , Failed to parse (Missing texvc executable; please see math/README to configure.): \epsilon

) Failed to parse (Missing texvc executable; please see math/README to configure.): \longrightarrow
(q2, y1)

See also[link]

• Stack machine
• Context-free grammar
• Finite automaton

References[link]

External links[link]

• non-deterministic pushdown automaton, on Planet Math.
• JFLAP, simulator for several types of automata including nondeterministic pushdown automata

Jeffrey David Ullman (born November 22, 1942) is a renowned computer scientist. His textbooks on compilers (various editions are popularly known as the Dragon Book), theory of computation (also known as the Cinderella book), data structures, and databases are regarded as standards in their fields.

Early life and career[link]

Ullman received a Bachelor of Science degree in Engineering Mathematics from Columbia University in 1963 and his Ph.D. in Electrical Engineering from Princeton University in 1966. He then worked for several years at Bell Labs. From 1969 to 1979 he was a professor at Princeton. Since 1979 he has been a professor at Stanford University, where he is currently the Stanford W. Ascherman Professor of Computer Science (Emeritus). In 1995 he was inducted as a Fellow of the Association for Computing Machinery and in 2000 he was awarded the Knuth Prize. Ullman is also the co-recipient (with John Hopcroft) of the 2010 IEEE John von Neumann Medal, “For laying the foundations for the fields of automata and language theory and many seminal contributions to theoretical computer science.”^[1]

Ullman's research interests include database theory, data integration, data mining, and education using the information infrastructure. He is one of the founders of the field of database theory, and was the doctoral advisor of an entire generation of students who later became leading database theorists in their own right. He was the Ph.D. advisor of Sergey Brin, one of the co-founders of Google, and served on Google's technical advisory board. He is currently the CEO of Gradiance.

Books[link]

References[link]

1. ^ "IEEE John von Neumann Medal Recipients". IEEE. http://www.ieee.org/portal/pages/about/awards/pr/vonneupr.html. Retrieved 2010-02-04. 

External links[link]

• Jeffrey Ullman's website

Rajendra Kumar (20 July 1929 – 12 July 1999) was one of the most successful Indian Bollywood actors in the 1960s and 1970s. He also produced several films in the 1980s starring his son Kumar Gaurav.

He was born in a Punjabi Hindu family in Sialkot, in the West Punjab province of British India, currently in Pakistan.^[1]

Career[link]

Rajendra Kumar made his debut in the 1950 film Jogan in which he starred opposite Dilip Kumar and Nargis. He then shot to fame^{[citation needed]} in the film Mother India in 1957 in which he played Nargis's son. His first major success as a romantic leading man^{[citation needed]} was in Amit Saxenas's musical Goonj Uthi Shehnai (1959), co-starring Ameeta.

The 1960s saw Kumar rise. There were times when he had six or seven films running in their silver jubilee weeks at the same time.^{[citation needed]} He became known as "Jubilee Kumar".^{[citation needed]}

He had many successful films including Dhool Ka Phool (1959), Dil Ek Mandir(1963), Mere Mehboob (1963), Sangam (1964), Arzoo (1965), Pyar Ka Sagar, Gehra Daag', Suraj (1966) and Talaash.^[2] He received the Filmfare Nomination for Best Actor for Dil Ek Mandir (1963), Ayee Milan Ki Bela (1964), Arzoo (1965), and as Best Supporting Actor for Sangam (1964).^[3]

From 1972 onwards, he faced competition from Rajesh Khanna. He was offered a role in the film Saajan Bina Suhaagan opposite Nutan. He then switched to character roles in the late 1970s and 1980s.

He also starred in a number of Punjabi films like Teri meri ek jindari.

In 1981 Rajendra introduced his son Kumar Gaurav in the film Love Story which he produced, directed and also starred in. The film was declared a blockbuster.^[4] Rajendra produced several other films starring his son. In 1986 he produced Naam with his son and his son's brother-in-law Sanjay Dutt in leading roles. The 1993 film Phool he again acted alongside him.

Rajendra appeared in only a few films after this and his last film appearance was a minor role in Deepa Mehta's film Earth in 1998.

Personal life[link]

He married Shukla and had a son and two daughters. His son Kumar Gaurav married Namrata Dutt, the daughter of actors Sunil Dutt and Nargis and sister of actor Sanjay Dutt.

Kumar acted with Sunil Dutt and Nargis in the film Mother India (1957) where Sunil Dutt and Rajendra Kumar played natural sons of Nargis. He had a special relationship with Dutt, who is quoted as having said that "Even though Rajendra Kumar did not win any award throughout his career, he was one of the most genuine human beings I have ever encountered. When I was struggling with the troubles related to the arrest of my son Sanjay Dutt and my house was repeatedly being searched by means of numerous police raids, Rajendra Kumar was the one who came to my rescue by staying at my house and ensuring that raids were conducted using due procedures, false evidences were not planted in the house and valuables were not stolen."^{[cite this quote]}

He died on 12 July 1999 of cancer, eight days before his 70th birthday.^{[citation needed]}

Honours and recognitions[link]

• Rajendra Kumar was honoured with the Padma Shri Award in 1969.
• He was also conferred with Justice of Peace honour and served as Honorary Magistrate.
• He was awarded the National Honour by late Pt. Jawaharlal Nehru simultaneously for “Kanoon” (Hindi) and “Mehandi Rang Lagyo” (Gujarati film).
• He received a special Shastri National Award and was associated with several charity schemes.^[5]

Awards and nominations[link]

Rajendra Kumar was nominated for Best Actor category three times.^{[clarification needed]}

Filmography[link]

Actor:

• Earth (1998) .... Refugee police
• Diya Aur Toofan (1969)
• "Andaz" (1995) TV series
• Phool (1993) .... Dharamraaj
• Insaaf Ka Khoon (1991) .... Judge Kumar
• Clerk (1989) .... Rahim U. Khan
• Main Tere Liye (1988) .... Shiva
• Lovers (1983) .... Christian Priest
• Rustom (1982) .... J. D. Mehta
• Yeh Rishta Na Tootay (1981) .... Police Inspector Vijay Kumar
• Saajan Ki Saheli (1981) .... Barrister Avinash Kumar
• Love Story (1981) .... Vijay Mehra
• Oh Bewafa (1980) .... R.K
• Dhan Daulat (1980) .... Raj Saxena
• Badla Aur Balidan (1980)
• Gunehgaar (1980)
• Bin Phere Hum Tere (1979) .... Jagdish Sharma
• Saajan Bina Suhagan (1978) .... Raj Kumar
• Aahuti (1978) .... CID Inspector Ram Prasad/Rocky
• Sone Ka Dil Lohe Ke Haath (1978) .... Shankar
• Daku Aur Mahatma (1977)
• Do Sholay (1977)
• Shirdi Ke Sai Baba (1977) .... Doctor (Pooja's husband)
• Mazdoor Zindabaad (1976) (uncredited) .... Ram Singh
• Do Jasoos (1975) .... Karamchand Jasoos
• Rani Aur Lalpari (1975) .... Rani's dad
• Sunehra Sansar (1975) .... Chandrashekhar
• Teri Meri Ik Jindri (1975) .... Jaggar Singh Fauji
• Do Sher (1974)(Punjabi Movie) .... Shera
• Dukh Bhanjan Tera Naam (1974) .... Boatsman
• Lalkar (The Challenge) (1972) .... Wing Commander Rajan Kapoor
• Aan Baan (1972) .... Suraj
• Gaon Hamara Shaher Tumhara (1972) .... Brij "Birju" Bhushan
• Gora Aur Kala (1972) .... Karan Singh/Kali Singh (Kalua)
• Tangewala (1972) .... Rai Bahadur Kishandas/Raju/Dilbahadur Khan
• Aap Aye Bahaar Ayee (1971) (as Rajinder Kumar) .... Rohit Kumar Verma
• Dharti (1970) .... Bharat
• Ganwaar (1970) .... Gopal Rai
• Geet (1970) .... Suraj 'Sarju' Kumar
• Mera Naam Joker (1970) (as Rajender Kumar) .... Mahender Kumar
• Anjaana (1969) .... Raju
• Shatranj (1969) (as Rajinder Kumar) .... Jai/Vijay/Shinranz
• Talash (1969) .... Raj Kumar 'Raju'
• Jhuk Gaya Aasman (1968) (as Rajinder Kumar) .... Sanjay/Tarun Kumar 'Battu' 'Pappu' Saxena
• Saathi (1968) .... Ravi
• Aman (1967) .... Dr. Gautamdas
• Palki (1967) .... Naseem Baig
• Suraj (1966) .... Suraj Singh
• Arzoo (1965) (as Rajinder Kumar) .... Gopal/Sarju
• Ayee Milan Ki Bela (1964) (as Rajinder Kumar) .... Shyam
• Sangam (1964) .... Magistrate Gopal Verma
• Zindagi (1964) .... Rajendra "Rajan"
• Akeli Mat Jaiyo (1963) (as Rajendrakumar) .... Prince Amardeep
• Amar Rahe Yeh Pyaar (1963)
• Dil Ek Mandir (1963) .... Dr. Dharmesh
• Gehra Daag (1963) .... Shanker
• Hamrahi (1963) (as Rajender Kumar) .... Shekhar
• Mere Mehboob (1963) .... Anwar
• Aas Ka Panchhi (1961) .... Rajan 'Raju' Khanna
• Dharmputra (1961) (uncredited) .... Special appearance
• Gharana (1961) .... Kamal
• Pyaar Ka Saagar (1961) .... Kishen Chand Gupta
• Sasural (1961) .... Shekhar
• Zindagi Aur Khwab (1961) .... Inspector Manoj
• Kanoon (1960) .... Advocate Kailash Khanna
• Maa Baap (1960) .... Raj Kumar 'Raju'
• Mehndi Rang Lagyo (1960) .... Anil
• Patang (1960) (as Rajender Kumar) .... Dr. Rajan
• Chirag Kahan Roshni Kahan (1959) .... Dr. Anand
• Dhool Ka Phool (1959) (as Rajinder Kumar) .... Mahesh Kapoor
• Do Behnen (1959)
• Goonj Uthi Shehnai (1959) .... Kishan
• Santan (1959)
• Devar Bhabhi (1958)
• Ghar Sansar (1958) .... Deepak
• Khazanchi (1958) .... Harish Mohan
• Talaaq (1958) .... Ravi Shankar Chaube
• Mother India (1957) .... Ramu
• Ek Jhalak (1957)
• Aawaz (1956) .... Ashok
• Toofan Aur Deeya (1956) .... Satish Sharma/Master-Ji
• Vachan (1955) .... Kishore
• Jogan (1950) .... Vijay's friend

Producer:

• The Jungle Book (1994) (co-executive producer) (co-producer)
• Phool (1993) (producer)
• Jurrat (1989) (producer)
• Naam (1986) (producer)
• Lovers (1983) (producer)
• Love Story (1981) (producer)

Presenter:

• The Train (1970)
• Ganwaar (1970)
• Talash (1969)
• Phool Aur Patthar (1966)

Editor:

• Jurrat (1989)

Director:

• Love Story (1981)

Soundtrack:

• Mere Mehboob (1963) (performer: "Mere Mehboob Tujhe", "Allah Bachaye", "Tere Pyar Mein Dildar", "Janeman Ek Nazar", "Yaad Mein Teri", "Tumse Izhar e Haal", "Mere Mehboob Mein Kya", "Ae Husn Zara Jaag", "Yaad Mein (revival)")

Thanks:

• Mera Naam Joker (1970) (acknowledgment) (as Rajender Kumar)

Self:

• Raj Kapoor (1987) .... Himself (during funeral)
• Star (1982) .... Himself (Guest Appearance)
• Shrimanji (1968) .... Himself
• Kala Bazar (1960) .... Himself

Archive Footage:

• Film Hi Film (1983) (uncredited)

Footnotes[link]

External links[link]

• Rajendra Kumar at the Internet Movie Database
• On Rajendra Kumar's Contribution to Indian Cinema
• Rajendra Kumar profile at Rediff.com

v t e Bollywood (Hindi cinema) Directors · Actors · Playback singers · Music Directors · Songs · Bibliography Hindi films A–Z—Highest-grossing Films by year: 1930s · 1940 · 1941 · 1942 · 1943 · 1944 · 1945 · 1946 · 1947 · 1948 · 1949 · 1950 · 1951 · 1952 · 1953 · 1954 · 1955 · 1956 · 1957 · 1958 · 1959 · 1960 · 1961 · 1962 · 1963 · 1964 · 1965 · 1966 · 1967 · 1968 · 1969 · 1970 · 1971 · 1972 · 1973 · 1974 · 1975 · 1976 · 1977 · 1978 · 1979 · 1980 · 1981 · 1982 · 1983 · 1984 · 1985 · 1986 · 1987 · 1988 · 1989 · 1990 · 1991 · 1992 · 1993 · 1994 · 1995 · 1996 · 1997 · 1998 · 1999 · 2000 · 2001 · 2002 · 2003 · 2004 · 2005 · 2006 · 2007 · 2008 · 2009 · 2010 · 2011 · 2012