# Tagged Questions

16 views

### Regular Expression Similarity Check

I was solving Formal Language and Automata Theory for a competitive exam, whence I came upon this following question: The regular expression 0*(10*)* denotes same set as: 0(0+10)* (0+1)10(0+1) ...
35 views

### Number of states of a finite automaton recognizing all words beginning with some fixed string $x$

For a string $x \in \{a,b\}^\ast$ with $|x| = n$, how many states are required for an FA accepting the language of all strings in $\{a,b\}$ that begin with $x$? For each of these states, describe the ...
39 views

### Basic Question about ambiguity of Grammar

I saw one book in Computation Course. I take a picture from this book, and in this book say why (or not) the following grammar is ambiguous? I couldn't find any solution to prove it's ambiguous. ...
38 views

### PDA and Some language Grammar inference

L1={$w^*$| w=x and $x \in \Sigma^*$} L2={$ww^R ww^R$| $w \in ( \Sigma + \Sigma)^*$} L3={$w | w=xy, x,y \in \Sigma^*$, y is a substring of x} a) there is a PDA(push down automata) that accept ...
60 views

### Challenge on Property of Complement in Language

We have: and M be a finite automata. Suppose d(M) be a deterministic automata that equivalence to M. if $M_1$ and $M_2$ be two finite automata, $M_1 + M_2$ is the finite automata such that the ...
26 views

### Design an finite automata for 010 and 01? [duplicate]

I have tried below question for designing automata but didn't success . ...
12 views

### What are the classes in A.N. Maslov hierarchy of indexed languages corresponding to Chomsky Hierachy?

As we know,that classes in A.N. Maslov hierarchy of indexed languages of level 2 is in sensitive languages of Chomsky hierarchy. What are the classes in A.N. Maslov hierarchy of indexed languages ...
20 views

### Do automatons and formal grammars belong to formal systems

A formal system consists of a formal language, a formal grammar that generates the language, a set of axioms, and a set of inference rules. Are automatons also formal systems? Is an automaton ...
36 views

### Deterministic Push-Down Automata

Does there exist Deterministic Push-Down Automata for the language below. Any kind of answer will be highly appreciated! $$L =ba^nb^n U bba^nb^{2n}$$
94 views

106 views

### Proving $L=\{0^n \mid \text{n is a perfect square}\}$ is not a Regular Language without the Pumping Lemma

Is this a valid way of going about proving the proposition? Let $L = \{0^n \mid \text{n is a perfect square}\}$. The regular languages are closed under concatenation. So if $x \in L, y \in L$, then ...
92 views

### DFA Rejection State

I'm being asked to construct a DFA for the language over $\{0,1\}$ such that each string of five consecutive symbols contain at least two zeroes. In my construction, it seems to me that it would make ...
57 views

### Grammar outside the Chomsky Hierarchy

This grammar describes a language that may fall outside the Chomsky Hierarchy (CH): \begin{array}{l} S \to abAbba \\ A \to abA \mid bbaB \\ B \to aab \\ \lambda \to Aab \mid aB \\ \end{array} Going ...