Recent questions and answers in Theory of Computation

0 votes

0 answers

It is CFL or not
It is CFL or not $\{wa^n w^r |\ w\ \in (a+b)^*, n>=0 \}$

asked 2 days ago in Theory of Computation by Sandeep Verma (102 points) | 17 views

0 votes

1 answer

regular language and few statements
$L$ is a regular language over $\Sigma^*$ $X = \{ x |x\ belongs\ to\ \Sigma^*, |x|\ is\ between\ n\ to\ 2n-1\ \}$ $\exists w \in x, w \in L\ then\ L\ is\ infinite.$ $\exists, |w| >= 2n,\ w \in L\ then\ \exists x \in X$ Which one of the following statements are true ? (A) Only I (B) Only II (C) Both I and II (D) Neither I or II

answered 2 days ago in Theory of Computation by Satbir (1k points) | 11 views

+1 vote

1 answer

The language is context free or not
consider this language: L={(a^n b^n)^2 :n>=0} Is this context free?

answered 3 days ago in Theory of Computation by JAYKISHAN (110 points) | 26 views

0 votes

0 answers

Net Exam 2018 july
Consider following 2 grammars : G1: s-> sbs|a G2: s->aB|ab A->AB|a B->ABb|b Checks abouts their ambiguity

asked 4 days ago in Theory of Computation by ManeeshaRaj (102 points) | 2 views

+1 vote

1 answer

How atleast become 2^n?
Given An arbitary non-deterministic finite automation with N states,the maximum numer of states in an equivalent minimized DFA is atleast?

answered 4 days ago in Theory of Computation by Debargha Bhattacharj (1.3k points) | 7 views

0 votes

0 answers

Describe a non-deterministic pda with three states that accept the language 0^n 1^m {n<M<2n} by empty stack

asked 4 days ago in Theory of Computation by paraskk (102 points) | 2 views

0 votes

0 answers

Positive closures of any regular language will not contain epsilon?(True or False)

asked 4 days ago in Theory of Computation by Chirag Shilwant (102 points) | 4 views

0 votes

0 answers

Is a^nb^nc^m where n>m Context Free Language ?
$a^{n}b^{n}c^{m}$ where n >m

asked 4 days ago in Theory of Computation by Deuce (102 points) | 4 views

0 votes

1 answer

context free grammar (self doubts)
$S1\rightarrow aS1b$ $S1\rightarrow aAb$ $S1\rightarrow aBb$ $A\rightarrow aA/a$ $B\rightarrow Bb/b$ here v={S1,A,B} and T={a,b} $a){{a^{n}b^{m}:m>0,|n-m|>2}}$ $b)a^{n}b^{m}:,m>1,|n-m|>1$ $c)a^{n}b^{m}:,m>0,|n-m|>1$ $d)a^{n}b^{m}:n,m>0,|n-m|>0$ what is language generated by the CFG

answered 4 days ago in Theory of Computation by Satbir (1k points) | 7 views

+1 vote

1 answer

Which of the following are regular languages? [Source: Applied Course live session]

answered 5 days ago in Theory of Computation by Satbir (1k points) | 18 views

0 votes

1 answer

why L2 is not regular? [Source: Applied Course live session]

answered 5 days ago in Theory of Computation by Satbir (1k points) | 30 views

+1 vote

1 answer

checking if given languages are regular or not
Consider the following languages. Which one of the following statements is true ? (A) L1 is regular, L2 is non regular (B) L1 is non regular, L2 is regular (C) L1 is regular, L2 is regular (D) L1 is non regular, L2 is non regular My ... string and if it is, we can prove that L1 is regular, but how can L2 be regular as that order needs to be maintained!

answered 6 days ago in Theory of Computation by Debargha Bhattacharj (1.3k points) | 38 views

0 votes

1 answer

Post correspondence is itself decision on decidability how then it is ambiguous

answered 6 days ago in Theory of Computation by Debargha Bhattacharj (1.3k points) | 26 views

0 votes

1 answer

PETER LINZ-DFA
The minimum number of states for these 2 languages: L1={w: (n(a)-n(b)) mod 3=2} L2={w: (n(a)-n(b)) mod 3=0} I am getting 9 for both of them .Please verify:)

answered 6 days ago in Theory of Computation by Debargha Bhattacharj (1.3k points) | 9 views

0 votes

0 answers

Peter Linz Exercise 1.3 Question 12
Design a transducer to convert a binary string into octal. For example, the bit string 001101110 should produce the output 156. In this case, are we given only those binary strings whose lengths are multiples of 3? Are we reading the binary string in reverse or normally? Also, please provide the solution to this problem.

asked 6 days ago in Theory of Computation by GATE_aspirant_2021 (102 points) | 5 views

0 votes

0 answers

NO. OF STATES(DFA)
Construct a DFA having no. of c’s divisible by a or divisible by b. Having alphabet ={c} For such a question do we have any closed form formula?

asked Aug 17 in Theory of Computation by Doraemon (139 points) | 15 views

0 votes

0 answers

made easy toc
In the below question if we get HTH then player 1 wins right ? But it is not going to final state . Can anyone please explain the solution

asked Aug 15 in Theory of Computation by Manasa.M (119 points) | 20 views

0 votes

1 answer

Context free language
Is the given language CFL or not? Σ*-L={a^n b^n a^n| n>=1}

answered Aug 14 in Theory of Computation by user2525 (1.6k points) | 16 views

0 votes

0 answers

madeeasy TOC
Option a. language also generates aa when m=1 and n=0 but in the given transitions there is no transition for (q0,a) when it is first read when stack contains z0 as stack symbol then how it can accept all strings generated by language . Can anyone please explain the solution

asked Aug 13 in Theory of Computation by Manasa.M (119 points) | 14 views

0 votes

1 answer

Ambiguity of grammars
Consider the Language: L = {$a^{n}b^{n}c^{k}$, n,k ≥ 1} ⋃ {$a^{n}b^{k}c^{k}$, n,k≥ 1} Which is True? (a) All the Grammars generating L will be ambiguous. (b) There exists a G which is unambiguous. (c) Language L is unambiguous (d) None of the above

answered Aug 13 in Theory of Computation by user2525 (1.6k points) | 8 views

0 votes

1 answer

Selft doubt - Decidability
Given a TM, M accepts a set of 100 Strings is decidable?

answered Aug 13 in Theory of Computation by user2525 (1.6k points) | 52 views

0 votes

0 answers

Gateoverflow question - doubt
https://gateoverflow.in/311001/deletion-of-useless-symbols-from-a-grammar-self-doubt In the above question aren’t we supposed to delete the production A → b because at the end after removing the useless symbols, A is unreachable from the start symbol S. So, wont be the answer S → a only after removing useless symbols ?

asked Aug 12 in Theory of Computation by user2525 (1.6k points) | 14 views

0 votes

2 answers

Relation between A,B and C
Let A= (a + b)* ab (a + b)*, B= a*b* and C= (a + b)*. Then the relation between A, B and C: A. A+B= C B. $A^{R}+B^{R}=C$ C. $A^{R}$+B= C D. None of these

answered Aug 12 in Theory of Computation by user2525 (1.6k points) | 32 views

0 votes

1 answer

Family of Languages
The language of primes in unary is: Regular CFL CSL DCFL

answered Aug 12 in Theory of Computation by Hirak (1.3k points) | 6 views

0 votes

1 answer

Deterministic FA
What are the number of final states in minimal DFA, where Σ= {a, b}, if every string starts with “aa” and length of string is not congruent to 0 (mod 4). A. 7 B. 6 C. 3 D. 5

answered Aug 12 in Theory of Computation by Hirak (1.3k points) | 16 views

0 votes

0 answers

Mapping reducibility doubt
I have read that if A<=B then A cannot be harder than B. I am still unable to solve this using that: If L' is semidecidable, L can be either decidable or semidecidable. So is false? Since it says L is semidecidable. L is RE, L' can be RE or ... RE or not even RE. So False. Answer key: 1 but explanation is not given. Kindly tell me the flaw in my approach. Thank you.

asked Aug 12 in Theory of Computation by DukeThunders (208 points) | 6 views

0 votes

0 answers

Number of derivations and height of parse tree in GNF

asked Aug 11 in Theory of Computation by DukeThunders (208 points) | 12 views

0 votes

0 answers

DFA accepting strings of 0’s and 1’s where the integer equivalent of the binary string is congruent to r mod n

asked Aug 11 in Theory of Computation by DukeThunders (208 points) | 9 views

0 votes

0 answers

ACE Workbook - Finite automata and Regular Language

asked Aug 11 in Theory of Computation by user2525 (1.6k points) | 5 views

0 votes

0 answers

Which of these machines can accept ambiguous grammar?

asked Aug 11 in Theory of Computation by DukeThunders (208 points) | 8 views

0 votes

0 answers

Number of states in epsilon and epsilon free NFA
Is there any relation between the number of states in an epsilon NFA and epsilon free NFA for the same language?

asked Aug 11 in Theory of Computation by DukeThunders (208 points) | 7 views

0 votes

2 answers

Complement of Context Free Language
I have read that CFL is not closed under complementation. I read somewhere that complement of CFL is CSL. I am not sure if I remember it correctly. Answer is given as D here. Kindly clarify my doubt. Thank you.

answered Aug 11 in Theory of Computation by Hirak (1.3k points) | 11 views

0 votes

1 answer

Regular expression doubt
Please explain the solution. Thank you.

answered Aug 11 in Theory of Computation by user2525 (1.6k points) | 6 views

0 votes

1 answer

Epsilon NFA doubt
Please show the approach. I am not fully aware of how delta star works. Does it mean applying epsilon *, a, epsilon * on qo state? Kindly explain. Thank you.

answered Aug 11 in Theory of Computation by user2525 (1.6k points) | 6 views

0 votes

1 answer

NFA with epsilon moves - Automata theory ( Testbook Test Series )

answered Aug 11 in Theory of Computation by Hirak (1.3k points) | 9 views

0 votes

0 answers

Made Easy workbook - Finite Automata
While doing reversal of a Finite automata, we change the arrows and interchange the final and initial states. But if there are more than one final state in F.A. are we supposed to merge the final states into one final state and then do the reversal of the finite automata. Is it the correct procedure for reversal of finite automata wth multiple final states ?

asked Aug 11 in Theory of Computation by user2525 (1.6k points) | 6 views

0 votes

1 answer

Number of states in DFA
1. A minimal DFA accepting the language $L = \{w|w ∈ (a,b,c) ^∗\}$, the number of a’s, b’s and c’s in w are divisible by $2, 3$ and $4$ respectively has ________ number of states Answer is given as 24 but isn’t 12 (lcm of 2,3,4) enough?

answered Aug 10 in Theory of Computation by Satbir (1k points) | 20 views

+1 vote

1 answer

Regular Language - Theory of Computation
Which of the following are regular languages ? $wxw^R ( w ∈ (a,b)^* , x ∈ (a,b)^* )$ $wxw^R ( w ∈ (a,b)^* , x ∈ (a,b)^+ )$ $wxw^R ( w ∈ (a,b)^+ , x ∈ (a,b)^* )$ $wxw^R ( w ∈ (a,b)^+ , x ∈ (a,b)^+ )$ $wxw ( w ∈ (a,b)^* , x ∈ (a,b)^* )$ ... $wxw ( w ∈ (a,b)^+ , x ∈ (a,b)^* )$ $wxw ( w ∈ (a,b)^+ , x ∈ (a,b)^+ )$ Here $w^R$ is reversal of string $w$.

answered Aug 10 in Theory of Computation by Satbir (1k points) | 13 views

0 votes

0 answers

DFA Practice question
Q1: Construct the minimal finite automata that accept all the strings of 0's & 1's is where the integer equivalent is congruent to 1(mod 4). What is the no. of states in minimal finite automata? Q2: Construct the minimal finite automata that accept all ... to 5(mod 8) has __________ no. of states. Please show the minimal DFA of at least one of the questions. Thank you.

asked Aug 10 in Theory of Computation by DukeThunders (208 points) | 4 views

0 votes

0 answers

TOC practice question on CFG
L = {$x^{a}y^{a}$: a ≥ 1} I. $L^{3}$ is context free. II. ⌈√L⌉ is not context free. Which of the following is correct? (a) I only (b) II only (c) Both I and II (d) None of the above The answer is given A) What are the languages represented by $L^{3}$ and ⌈√L⌉?

asked Aug 10 in Theory of Computation by DukeThunders (208 points) | 4 views