# Tagged Questions

Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

13 views

### Unable to construct Context-free Grammar from Pushdown Automaton $a^n b^m$

I have a big problem with solving this $L = \{\,a^n b^m \mid 0 \le n \le m \le 2n\,\}$. I've try my best. I want to construct it. Please help guys.
29 views

### Given an automatic sequence, what monoid endomorphisms fix the corresponding morphic word?

Recall that every automatic sequence forms a morphic word. Given an automatic sequence, how can one construct a monoid endomorphism to define the corresponding morphic word? For example, consider the ...
58 views

### finite state machine transition table problem

I have the following question which im not able to do. I have done things with DFA/NFA's before but this is the first time ive seen a question like this, I have been looking for similar questions in ...
43 views

### What are some properties that the regular languages are not closed under?

In a standard Theory of Computation class, one learns a variety of closure properties of regular languages, including but not limited to: homomorphism, inverse homomorphism, union, complement, ...
49 views

### Languages acceptable with just a single final state

For a given regular language $L$ we can always find a corresponding automaton with exactly one initial state, this is quite a common result and in most textbooks even non-deterministic automata are ...
47 views

### FSM to add two integer

Design a Mealy machine to add two integer(binary number). I can not determine how to deal with the carry.And what to do with the last carry generated.
3 views

### Turing machine with k-dimensional tape or k-regular tree

The statement I read is " In a k-dimensional tape, cells corresponds to elements of free commutative group of k generators. s. There are 2k shifts, which correspond to addition of a generator ...
35 views

### comparing two strings with Turing Machine

Reading about Multitape Turing Machines and coming across this exercise: Construct a Turing Machine, that can "tell" if a word w1 on strip 1 matches w2 on strip 2. Given approach : Compare the states ...
25 views

### Which of the following string have two or more parse trees?

Consider the following ambiguous grammar: $S→A|BC$ $A→aAC|B$ $C→bCc|c$ $B→aBb|\in$ Which of the following string have two or more parse trees? $aaabbbbbcc$ $aaabb$ $aabb$ None of these My ...
53 views

### Identify inherently ambiguous languages

Which of the following languages is/are inherently ambiguous languages? $L_1=\{a^nb^nc^m|m,n\geq0\}\cup\{a^nc^c|n\geq0\}$ $L_2=\{a^nb^nc^m|m,n\geq0\}\cup\{c^mb^na^n|m,n\geq0\}$ My attempt: A ...
8 views

### Are transactions across petri net assumed to be running in parallel or there is always a predefined order?

I have a place $P$ with 3 marks in it and two outgoing immidiate Transitions [$t1, t2$] that require 1 token to fire. How marks flow are determined in Petri Net? Are there any Petri Net flavour ...
20 views

### Find the classes of $L_1=\{w|n_a(w)|n_b(w)=n_c(w)\}$ and $L_2=\{wxw^R|w,x\in(0,1)\}$

$L_1=\{w|n_a(w)|n_b(w)=n_c(w)\}$ $L_2=\{wxw^R|w,x\in(0,1)\}$ My attempt: $L_2$ seems regular since it's finite. $L_1$ is DCFL since we can identify strings of $L_1$ using single stack, first we ...
27 views

### Subset of regular language $a^*$

Given $L\subseteq a^*$, then $L$ is definitely decidable $L$ is definitely Turing – recognizable $L$ may not be Turing – recognizable. $L$ is regular My attempt: $L$ may not be regular, ...
35 views

### Is the language regular

We have to check, if the given two languages are regular or not. L={w |each prefix of w has more 0 than 1} L'={w|w has a prefix with more 0 than 1}. I tried something like this: If L regular, ...
11 views

18 views

### If $G$ is $LL(k)$, then $L(G)$ is a deterministic context free language.

In formal language theory, a context-free language (CFL) is a language generated by some context-free grammar (CFG). For every grammar, If the correct production can be deduced from the partially ...
23 views

### Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$

Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$, then which of the following statements are true? $L_1\cup L_2$ is a ...
37 views

### Turing Machine make use of another Turing Machine

I am expected to formally construct a deterministic TM to compute a function. I already have a TM for $f(x)$. How can I make use it formally while constructing $g(x)$? $g(x)$ is like in the followig ...
38 views

17 views

### generating transition diagram and accepted language from prime number expression

I have the following expression and have to generate the diagram $(M(5))$ and accepted language $(M(5))$ for it, the issue is that I am having trouble even understanding what the expression is saying. ...
34 views

### Find $A^n$ for n=0,1, and 3: Languages and Finite State Machines

The question is: Let $A$={11,00}. Find $A^n$ for n=0,1, and 3. Would i be right in thinking that $A^0$ = {λ} $A^1$ = {11,00} $A^3$ = {111111,111100,110011,110000,000011,000000,001100,001111}. if ...
22 views

### What is an automata network?

I've tried Wikipedia and Google as first steps, but while I've found some interesting papers and articles, and a couple expensive textbooks, I've yet to find a clear definition of an automata network ...
51 views

### What's the meaning this DOT notation?

I'm reading a chapter in a Model Checking book. I came across this chapter "Symbolic Model Checking", in which the author mentions Fixed Point representation. I don't know how to explain the context, ...
49 views

### Can a regular grammar be ambiguous?

An ambiguous grammar is a context-free grammar for which there exists a string that has more than one leftmost derivation, while an unambiguous grammar is a context-free grammar for which every valid ...
22 views

### accepted language notation for CFG for recurring 1's and 0's

Hi I often have trouble with the notation when having to write the accepted language for a finite automata or CFG. Right know I have a CFG that generates groups of any number of 1's followed by any ...