FORMAL LANGUAGES AND AUTOMATA THEORY

Which of the following statements is/are False?

Enumerator is a Turing machine with

The language $ \{a^m b^n c^{m+n} \mid m, n \ge 1\} $ is

The maximum number of states of a DFA converted from an NFA with $ n $ states is

If $ L_1 $ and $ L_2 $ are context-free languages, $ L_1 - L_2 $ is

Which of the following does not have left recursions?

Let N be an NFA with $ n $ states and let M be the minimized DFA with $ m $ states recognizing the same language. Which of the following is necessarily true?

_____ is the acyclic graphical representation of a grammar.

A minimum state deterministic FA accepting the language $ L = \{w \mid w \in \{0, 1\}^*\} $ where number of 0's and 1's in w are divisible by 3 and 5 respectively, has

The construction time for DFA from an equivalent NFA ($ m $ number of node) is

Tabulate Chomsky hierarchy of grammar with an example for each.

Design a finite state machine abstract model for Parity checker.

Construct an NFA that will accept string of 0's, 1's and 2's beginning with a 0's followed by odd number of 1's and ending with any number of 2's.

Construct a push-down automata that accepts the following language: $ L = \{uawb : u \text{ and } w \in (a,b)^* \text{ and } |u| = |w|\} $

Design a Turing machine (TM) to compute $ n \mod 2 $.

Design a DFA corresponding to regular expression $ 1^*(10)^* $

Consider the grammar: $ S \rightarrow AB \mid BC $, $ A \rightarrow BA \mid a $, $ B \rightarrow CC \mid b $, $ C \rightarrow AB \mid a $. Use the CYK algorithm to determine whether the given string "baaba" is in $ L(G) $ or not.

Suppose L is context free and R is regular, justify your answer with the help of example:
(i) Is $ L - R $ necessarily context free?
(ii) Is $ R - L $ necessarily context free?

Show that the language $ L = \{a^{n!} : n \ge 0\} $ is not regular or not context-free language.

Let G be a context-free grammar in Chomsky normal form that contains $ b $ variable. Show that if G generates some string using a derivation with at least $ 2^b $ steps, then $ L(G) $ is infinite.

State and prove pumping lemma for regular sets.

Show given grammar over alphabet {a, b}, verify whether it is ambiguous or unambiguous : $ S \rightarrow aSa \mid bSb \mid a \mid b \mid \epsilon $

Show that the sum function $ f(x, y) = x + y $ is primitive recursive.

Construct a PDA that accepts the language $ L = \{a^{2n}bc \mid n \ge 0\} $ by final state and empty stack.

Which of the following statements is/are False?

Enumerator is a Turing machine with

The language $\{a^m b^n c^{m+n} \mid m, n \ge 1\}$ is

The maximum number of states of a DFA converted from an NFA with $n$ states is

If $L_1$ and $L_2$ are context-free languages, $L_1 - L_2$ is

Which of the following does not have left recursions?

Let N be an NFA with $n$ states and let M be the minimized DFA with $m$ states recognizing the same language. Which of the following is necessarily true?

_____ is the acyclic graphical representation of a grammar.

A minimum state deterministic FA accepting the language $ L = {w \mid w \in {0, 1}^*} $ where number of 0's and 1's in w are divisible by 3 and 5 respectively, has

The construction time for DFA from an equivalent NFA ($ m $ number of node) is

Tabulate Chomsky hierarchy of grammar with an example for each.

Design a finite state machine abstract model for Parity checker.

Construct an NFA that will accept string of 0's, 1's and 2's beginning with a 0's followed by odd number of 1's and ending with any number of 2's.

Construct a push-down automata that accepts the following language: $ L = {uawb : u \text{ and } w \in (a,b)^* \text{ and } |u| = |w|} $

Design a Turing machine (TM) to compute $n \mod 2$.

Design a DFA corresponding to regular expression $1^*(10)^*$

Consider the grammar: $S \rightarrow AB \mid BC$, $A \rightarrow BA \mid a$, $ B \rightarrow CC \mid b $,$ C \rightarrow AB \mid a $. Use the CYK algorithm to determine whether the given string "baaba" is in $L(G)$ or not.

Suppose L is context free and R is regular, justify your answer with the help of example:
(i) Is $L - R$ necessarily context free?
(ii) Is $R - L$ necessarily context free?

Show that the language $L = \{a^{n!} : n \ge 0\}$ is not regular or not context-free language.

Let G be a context-free grammar in Chomsky normal form that contains $b$ variable. Show that if G generates some string using a derivation with at least $2^b$ steps, then $L(G)$ is infinite.

State and prove pumping lemma for regular sets.

Show given grammar over alphabet {a, b}, verify whether it is ambiguous or unambiguous : $ S \rightarrow aSa \mid bSb \mid a \mid b \mid \epsilon $

Show that the sum function $f(x, y) = x + y$ is primitive recursive.

Construct a PDA that accepts the language $L = \{a^{2n}bc \mid n \ge 0\}$ by final state and empty stack.

• Post-correspondence problem
• Chomsky normal form
• Multistack Turing machine
• Pumping lemma for CFL

Definition of a language L with alphabet {a} is given as $ L = \{a^{nk} \mid k > 0 \}, $ and n is a positive integer constant. What is the minimum number of states needed in a DFA to recognize L?

Which of the following versions of Unix came up with YACC first?

A pushdown automata can be represented as $ PDA = \epsilon \text{-} NFA + [\text{stack}] $.

A language accepted by deterministic pushdown automata is closed under which of the following?

A _____ is context free grammar with atmost one non-terminal in the right handside of the production.

The lexical analysis for a modern language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

Let $ L = \{w \in (0+1)^* \mid w \text{ has even number of 1s}\} $, i.e., L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

What is the minimum number of states in deterministic finite automata (DFA) for string starting with $ ba^2 $ and ending with a over alphabet {a, b}?

The decision problem is the function from string to

A language L may not be accepted by a turing machine if

Write the context-free grammar to create palindrome over {a, b}.

Construct a DFA which accepts the set of all binary strings that interpreted as binary representation of an unsigned decimal integer, is divisible by 5.

Design a turing machine to compute the sum of two positive integers m and n.

Design a NPDA for accepting the string $ L = $ set of all palindrome over {a, b} by the empty stack and by final state.

Construct finite automaton corresponding to the regular expression: $ (a+b)^*c d^*e $

Explain the multi-tape version of turing machine and its significance.

Show given grammar over alphabet {a, b} verify whether it is ambiguous or unambiguous : $ S \rightarrow a / abSb / aAb $, $ A \rightarrow bS / aAAb $

Show that $ L = $ palindrome over {a, b} is not regular.

Prove that if L is generated by a CFG, then L is accepted by a non-deterministic PDA by empty stack.

Design a pushdown automaton for the following context-free grammar: $ S \rightarrow aB \mid bA $, $ A \rightarrow aS \mid bAA \mid a $, $ B \rightarrow bS \mid aBB \mid b $

Design a turing machine that accepts all palindromes over $ \Sigma = \{a, b\} $.

Explain Myhill-Nerode theorem for minimization of automata with suitable example.

Prove that if L is the language generated by an unrestricted grammar $ G=(N,T,P,S) $, then L is recognized by a turing machine.

Design a pushdown automata for accepting the string for the language $ L = \{WW^R \mid W \in (a,b)^*\} $ by the empty stack as well as final state.

Definition of a language L with alphabet {a} is given as L = \{a^{nk} \mid k > 0 \}, and n is a positive integer constant. What is the minimum number of states needed in a DFA to recognize L?

Which of the following versions of Unix came up with YACC first?

A pushdown automata can be represented as $ PDA = \epsilon \text{-} NFA + [\text{stack}] $.

A language accepted by deterministic pushdown automata is closed under which of the following?

A _____ is context free grammar with atmost one non-terminal in the right handside of the production.

The lexical analysis for a modern language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

Let $L = \{w \in (0+1)^* \mid w \text{ has even number of 1s}\}$, i.e., L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

What is the minimum number of states in deterministic finite automata (DFA) for string starting with $ba^2$ and ending with a over alphabet {a, b}?

The decision problem is the function from string to

A language L may not be accepted by a turing machine if

Write the context-free grammar to create palindrome over {a, b}.

Construct a DFA which accepts the set of all binary strings that interpreted as binary representation of an unsigned decimal integer, is divisible by 5.

Design a turing machine to compute the sum of two positive integers m and n.

Design a NPDA for accepting the string $L =$ set of all palindrome over {a, b} by the empty stack and by final state.

Construct finite automaton corresponding to the regular expression: $(a+b)^*c d^*e$

Explain the multi-tape version of turing machine and its significance.

Show given grammar over alphabet {a, b} verify whether it is ambiguous or unambiguous : $ S \rightarrow a / abSb / aAb $,$ A \rightarrow bS / aAAb $

Show that $L =$ palindrome over {a, b} is not regular.

Prove that if L is generated by a CFG, then L is accepted by a non-deterministic PDA by empty stack.

Design a pushdown automaton for the following context-free grammar: $ S \rightarrow aB \mid bA $, $A \rightarrow aS \mid bAA \mid a$, $B \rightarrow bS \mid aBB \mid b$

Design a turing machine that accepts all palindromes over $\Sigma = \{a, b\}$.

Explain Myhill-Nerode theorem for minimization of automata with suitable example.

Prove that if L is the language generated by an unrestricted grammar $G=(N,T,P,S)$, then L is recognized by a turing machine.

Design a pushdown automata for accepting the string for the language $ L = {WW^R \mid W \in (a,b)^*} $ by the empty stack as well as final state.

• Minimization of automata
• Type 2 grammar (Context free)
• NP-hard problem
• Pumping lemma for CFL

The word 'formal' in formal languages means

Which of the following statements is true?

Which of the following pairs of regular expressions are equivalent?

Which of the following pairs have DIFFERENT expressive powers?

Definition of a language L with alphabet {a} is given as $ L = \{a^{nk} \mid k > 0 \text{ and n is a positive integer constant}\} $. What is the minimum number of states needed in a DFA to recognize L?

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP complete (NPC)?

Let L1 be a recursive language. Let L2 and L3 be languages that are not recursively enumerable but recursive. Which of the following statements is not necessarily true?

A PDM behaves like an FSM when the number of auxiliary memory it has, is

Define Turing machine in brief.

A finite automaton with _____ is equivalent to push-down automata.

Consider the set of strings on {0, 1} defined by the requirements below. For each, construct an accepting dfa:
(i) Every 00 is followed immediately by a 1. For example, the strings 101, 0010, 001001 are in the language, but 0001 and 00100 are not.
(ii) All strings containing 00 but not 000.
(iii) The leftmost symbol differs from the rightmost one.
(iv) Every substring of four symbols has at most two 0's. For example, 001110 and 011001 are in the language, but 10010 is not since one of its substrings, 0010, contains three zeros.

Construct the regular grammar accepting the following language: $ L = w \in \{a, b\}^* \mid w \text{ is a string over } \{a, b\} $ $ \text{ such that the number of b's is } 3 \mod 4 $

Let $ G = (V, T, S, P) $ be a right-linear grammar. Prove that the language generated using the grammar G is a regular.

Construct a Moore machine equivalent to the Mealy machine M defined by the following Table 1 state transitions:

Prove the following equation : $ (1+00^*1) + (1+00^*1)(0+10^*1)^*(0+10^*1) $ = $ 0^*1(0+10^*1)^* $

Using the pumping lemma theorem, show that the following sets are not regular:

$ L = \{a^n b^l a^k : k \ge n+l\} $

$ L = \{w : n_a(w) = n_b(w)\} $

$ L = \{ww w^R : w \in \{a,b\}^*\} $

Convert the grammar into Chomsky normal form: $ S \rightarrow aB \mid AB $, $ A \rightarrow aab \mid \lambda $, $ B \rightarrow bbA $

Show that the family of unambiguous context-free languages is not closed under union.

Construct an npda corresponding to the grammar: $ S \rightarrow aABB \mid aAA $, $ A \rightarrow aBB \mid a $, $ B \rightarrow bBB \mid A $

Construct Turing machines that will accept the following languages on {a, b}:

$ L = \{w : n_a(w) = n_b(w)\} $

$ L = \{wcw : w \in \{a,b\}^*\} $

Design a Turing machine with no more than three states that accepts the language $ L(a(a+b)^*) $. Assume that $ \Sigma = \{a, b\} $. Is it possible to do this with a two-state machine?

Let G be an undirected graph. An Euler circuit of the graph is a simple cycle that includes all edges. The Euler Circuit Problem (EULER) is to decide if G has an Euler circuit. Show that EULER is not NP-complete.

The word 'formal' in formal languages means

Which of the following statements is true?

Which of the following pairs of regular expressions are equivalent?

Which of the following pairs have DIFFERENT expressive powers?

Definition of a language L with alphabet {a} is given as $ L = \{a^{nk} \mid k > 0 \text{ and n is a positive integer constant}\} $. What is the minimum number of states needed in a DFA to recognize L?

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP complete (NPC)?

Let L1 be a recursive language. Let L2 and L3 be languages that are not recursively enumerable but recursive. Which of the following statements is not necessarily true?

A PDM behaves like an FSM when the number of auxiliary memory it has, is

Define Turing machine in brief.

A finite automaton with _____ is equivalent to push-down automata.

Consider the set of strings on {0, 1} defined by the requirements below. For each, construct an accepting dfa:
(i) Every 00 is followed immediately by a 1. For example, the strings 101, 0010, 001001 are in the language, but 0001 and 00100 are not.
(ii) All strings containing 00 but not 000.
(iii) The leftmost symbol differs from the rightmost one.
(iv) Every substring of four symbols has at most two 0's. For example, 001110 and 011001 are in the language, but 10010 is not since one of its substrings, 0010, contains three zeros.

Construct the regular grammar accepting the following language: $ L = w \in \{a, b\}^* \mid w \text{ is a string over } \{a, b\} $ $ \text{ such that the number of b's is } 3 \mod 4 $

Let $ G = (V, T, S, P) $ be a right-linear grammar. Prove that the language generated using the grammar G is a regular.

Construct a Moore machine equivalent to the Mealy machine M defined by the following Table 1 state transitions:

Prove the following equation : $ (1+00^*1) + (1+00^*1)(0+10^*1)^*(0+10^*1) $ = $ 0^*1(0+10^*1)^* $

Using the pumping lemma theorem, show that the following sets are not regular:

$ L = \{a^n b^l a^k : k \ge n+l\} $

$ L = \{w : n_a(w) = n_b(w)\} $

$ L = \{ww w^R : w \in \{a,b\}^*\} $

Convert the grammar into Chomsky normal form: $ S \rightarrow aB \mid AB $, $ A \rightarrow aab \mid \lambda $, $ B \rightarrow bbA $

Show that the family of unambiguous context-free languages is not closed under union.

Construct an npda corresponding to the grammar: $ S \rightarrow aABB \mid aAA $, $ A \rightarrow aBB \mid a $, $ B \rightarrow bBB \mid A $

Construct Turing machines that will accept the following languages on {a, b}:

$ L = \{w : n_a(w) = n_b(w)\} $

$ L = \{wcw : w \in \{a,b\}^*\} $

Design a Turing machine with no more than three states that accepts the language $ L(a(a+b)^*) $. Assume that $ \Sigma = \{a, b\} $. Is it possible to do this with a two-state machine?

Let G be an undirected graph. An Euler circuit of the graph is a simple cycle that includes all edges. The Euler Circuit Problem (EULER) is to decide if G has an Euler circuit. Show that EULER is not NP-complete.

Regular expressions are closed under

Extended transition function is

From the options given below, the pair having different expressive powers is

For the language $ \{a^p \mid p \text{ is a prime}\} $, the statement which holds true is

Which one of the following statements is true?

A class of language that is closed under

CFG can be recognized by

A given grammar is called ambiguous, if

The output of the Mealy machine depends

The logic of pumping lemma is a good example of

For each of the following languages, construct a DFA that accepts the language. In all cases, the alphabet is {0, 1}:
(i) {w : the length of w is divisible by three}
(ii) {w : 110 is not a substring of w}
(iii) {w : w contains at least five 1's}
(iv) {w : w contains the substring 1011}
(v) {w : w contains at least two 1's and at most two 0's}

State and proof pumping lemma for regular languages.

Using pumping lemma, show that the language $ A = \{ww \mid w \in \{0, 1\}^*\} $ is not regular.

Let A be a non-empty regular language. Prove that there exists an NFA that accepts A and that has exactly one accept state.

Convert each of the following regular expressions to an NFA: (i) $ (0 \cup 1) 1^* 000 (0 \cup 1)^* $ (ii) $ (((10)^*(001) \cup 10))^* $ (iii) $ (baa + abb)^* $

(a) Prove the following two properties: (i) Regular sets are closed over the intersection operation. (ii) Regular sets are closed over the union operation.
(b) Represent the language that contains strings over $ \Sigma = \{0, 1\} $ and has even number of 0's.
(c) Convert the following DFA to a regular expression:

(a) Construct context-free grammars that generate the following languages. In all cases $ \Sigma = \{a, b\} $: (i) $ a^*b $ (ii) $ (ab)^* $
(b) Construct a CFG for the set of non-negative odd integers.

Let A and B be context-free languages over the same alphabet $ \Sigma $.
(i) Prove that the union $ A \cup B $ of A and B is also context-free.
(ii) Prove that the concatenation AB of A and B is also context-free.
(iii) Prove that the star $ A^* $ of A is also context-free.

Determine a CFG without unit production equivalent to the CFG given below: $ S \rightarrow a \mid Xb \mid aYa \mid b \mid aa $, $ X \rightarrow Y $, $ Y \rightarrow b \mid X $

(a) Find the CNF (Chomsky Normal Form) for the following CFG: $ S \rightarrow ABA $, $ A \rightarrow aA \mid \epsilon $, $ B \rightarrow bB \mid \epsilon $
(b) Eliminate null productions from the following CFG: $ S \rightarrow Xa $, $ X \rightarrow aX \mid bX \mid \epsilon $
(c) Convert the following grammar to GNF: $ A_1 \rightarrow A_2 A_3 $, $ A_2 \rightarrow A_3 A_1 \mid b $, $ A_3 \rightarrow A_1 A_2 \mid a $

Construct npda that accepts the following languages on $ \Sigma = \{a, b, c\} $:
(i) $ L = \{a^n b^{2n} : n \ge 0\} $
(ii) $ L = \{wcw^R : w \in \{a,b\}^*\} $
(iii) $ L = \{w : n_a(w) = 2n_b(w)\} $

Design a PDA that accepts the language $ L = \{a^n b^m a^n : m, n > 0\} $

(a) Design a Turing machine that recognizes strings containing equal number of 0's and 1's.
(b) Let $ L_1 $ be recursive and $ L_2 $ recursively enumerable. Show that $ L_2 - L_1 $ is necessarily recursively enumerable.
(c) Define P, NP, NPH and NPC problems with example.

Regular expressions are closed under

Extended transition function is

From the options given below, the pair having different expressive powers is

For the language $ \{a^p \mid p \text{ is a prime}\} $, the statement which holds true is

Which one of the following statements is true?

A class of language that is closed under

CFG can be recognized by

A given grammar is called ambiguous, if

The output of the Mealy machine depends

The logic of pumping lemma is a good example of

For each of the following languages, construct a DFA that accepts the language. In all cases, the alphabet is {0, 1}:
(i) {w : the length of w is divisible by three}
(ii) {w : 110 is not a substring of w}
(iii) {w : w contains at least five 1's}
(iv) {w : w contains the substring 1011}
(v) {w : w contains at least two 1's and at most two 0's}

State and proof pumping lemma for regular languages.

Using pumping lemma, show that the language $ A = \{ww \mid w \in \{0, 1\}^*\} $ is not regular.

Let A be a non-empty regular language. Prove that there exists an NFA that accepts A and that has exactly one accept state.

Convert each of the following regular expressions to an NFA: (i) $ (0 \cup 1) 1^* 000 (0 \cup 1)^* $ (ii) $ (((10)^*(001) \cup 10))^* $ (iii) $ (baa + abb)^* $

(a) Prove the following two properties: (i) Regular sets are closed over the intersection operation. (ii) Regular sets are closed over the union operation.
(b) Represent the language that contains strings over $ \Sigma = \{0, 1\} $ and has even number of 0's.
(c) Convert the following DFA to a regular expression:

(a) Construct context-free grammars that generate the following languages. In all cases $ \Sigma = \{a, b\} $: (i) $ a^*b $ (ii) $ (ab)^* $
(b) Construct a CFG for the set of non-negative odd integers.

Let A and B be context-free languages over the same alphabet $ \Sigma $.
(i) Prove that the union $ A \cup B $ of A and B is also context-free.
(ii) Prove that the concatenation AB of A and B is also context-free.
(iii) Prove that the star $ A^* $ of A is also context-free.

Determine a CFG without unit production equivalent to the CFG given below: $ S \rightarrow a \mid Xb \mid aYa \mid b \mid aa $, $ X \rightarrow Y $, $ Y \rightarrow b \mid X $

(a) Find the CNF (Chomsky Normal Form) for the following CFG: $ S \rightarrow ABA $, $ A \rightarrow aA \mid \epsilon $, $ B \rightarrow bB \mid \epsilon $
(b) Eliminate null productions from the following CFG: $ S \rightarrow Xa $, $ X \rightarrow aX \mid bX \mid \epsilon $
(c) Convert the following grammar to GNF: $ A_1 \rightarrow A_2 A_3 $, $ A_2 \rightarrow A_3 A_1 \mid b $, $ A_3 \rightarrow A_1 A_2 \mid a $

Construct npda that accepts the following languages on $ \Sigma = \{a, b, c\} $:
(i) $ L = \{a^n b^{2n} : n \ge 0\} $
(ii) $ L = \{wcw^R : w \in \{a,b\}^*\} $
(iii) $ L = \{w : n_a(w) = 2n_b(w)\} $

Design a PDA that accepts the language $ L = \{a^n b^m a^n : m, n > 0\} $

(a) Design a Turing machine that recognizes strings containing equal number of 0's and 1's.
(b) Let $ L_1 $ be recursive and $ L_2 $ recursively enumerable. Show that $ L_2 - L_1 $ is necessarily recursively enumerable.
(c) Define P, NP, NPH and NPC problems with example.

Choose the correct alternatives for any seven of the following :

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Choose the correct answer for any seven of the following :

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Define any seven of the following :

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Answer the following:

Choose the correct option of the following (any seven) :

Answer the following: