Register

IT Gate 2004

769 views
1 votes
1 votes

Let M = (K, Σ, Г, Δ, s, F) be a pushdown automaton, where

K = (s, f), F = {f}, Σ = {a, b}, Г = {a} and 
Δ = {((s, a, ε), (s, a)), ((s, b, ε), (s, a)), (( s, a, ε), (f, ε)), ((f, a, a), (f, ε)), ((f, b, a), (f, ε))}.

Which one of the following strings is not a member of L(M)?

  1. aaa
  2. aabab
  3. baaba
  4. bab

This question has been asked previously in GO. But I am not getting it.

Can anybody please explain the meaning of each transition!? What does the Epsilon in the 1st 3 transitions stand for !? 

User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

7.2k
views
5 answers
47 votes
Ishrat Jahan asked Nov 2, 2014
7,186 views
GATE IT 2004 | Question: 41
Let $M=(K, Σ, \sigma, s, F)$ be a finite state automaton, where$K = \{A, B\}, Σ = \{a, b\}, s = A, F = \{B\},$\sigma(A, a) = A, \sigma(A, b) = B, \sigma(B, a) ... → aA, B → bA, B → \epsilon)$\{A → aA, A → bA, B → aB, B → bA, A → \epsilon)$
User Avatar
43.7k
views
9 answers
56 votes
Ishrat Jahan asked Nov 2, 2014
43,698 views
GATE IT 2004 | Question: 40
Let $M = (K, Σ, Г, Δ, s, F)$ be a pushdown automaton, where$K = (s, f), F = \{f\}, \Sigma = \{a, b\}, Г = \{a\}$ ... , (f, \epsilon))\}$.Which one of the following strings is not a member of $L(M)$?$aaa$aabab$baaba$bab$
User Avatar
6.6k
views
1 answers
26 votes
Ishrat Jahan asked Nov 1, 2014
6,642 views
GATE IT 2004 | Question: 9
Which one of the following statements is FALSE?There exist context-free languages such that all the context-free grammars generating them are ambiguousAn unambiguous ... finite set of string from some alphabet is always a regular language
User Avatar
9.2k
views
5 answers
28 votes
Ishrat Jahan asked Nov 1, 2014
9,168 views
GATE IT 2004 | Question: 7
Which one of the following regular expressions is NOT equivalent to the regular expression $(a + b + c)^*$?$(a^* + b^* + c^*)^*$(a^*b^*c^*)^*$((ab)^* + c^*)^*$(a^*b^* + c^*)^*$
User Avatar
Link Copied!